2 u014643765 u014643765 于 2015.07.09 16:01 提问

关于快速排序和归并排序的速度问题

#include
#include
#include
void mergerarray(int* src,int* tem,int start,int end)
{
int mid=(start+end)/2;
int l=start,k=start,r=mid+1;
while((l {
if(src[l] tem[k++]=src[l++];
else
tem[k++]=src[r++];
}
while(l tem[k++]=src[l++];;
while(r tem[k++]=src[r++];
for(l=start;l src[l]=tem[l];
}
void mergersort(int* src,int* tem,int start,int end)
{
if(start {
mergersort(src,tem,start,(start+end)/2);
mergersort(src,tem,(start+end)/2+1,end);
mergerarray(src,tem,start,end);
}
}
void quicksort(int* src,int start,int end)
{
int l=start,r=end;
int key=0;
if(start>=end)
return;
key=src[l];
src[l]=src[(start+end)/2];
src[(start+end)/2]=key;
while(l {
while((l r--;
if(l src[l++]=src[r];
while((l=src[l]))
l++;
if(l<r)
src[r--]=src[l];
}
src[l]=key;
quicksort(src,start,l-1);
quicksort(src,l+1,end);
}
int main(void)
{
int* src=NULL;
int* tem=NULL;
int n=10000000;
int i=0;
clock_t start,end;
double duration;
src=(int*)malloc(n*sizeof(int));
tem=(int*)malloc(n*sizeof(int));
for(i=0;i<n;i++)
src[i]=rand();
start=clock();
//////////////排序/////////////////////////////////
// mergersort(src,tem,0,n-1);
quicksort(src,0,n-1);
////////////////////////////////////////////////
end=clock();
duration=(end-start)*1000/CLOCKS_PER_SEC;
printf("耗时%f毫秒\n\n",duration);
free(src);
free(tem);
return 0;
}

                 快速排序(ms)   归并排序(ms)

1百万数据 141 187
1千万数据 4119 2262

当排序的数据量不大时,快排的速度大于归并排序,
当排序的数据比较大时,归并排序的速度大于快排,
是不是cache命中率的原因
哪位大神可以解释一下

2个回答

caozhy
caozhy   Ds   Rxr 2015.07.09 16:09

如果数据是基本有序的,那么归并更快一点不奇怪。也可能是cache的原因。要用性能热点分析工具才知道

frank_20080215
frank_20080215   2015.07.09 17:00

快速排序快速排序的最坏情况基于每次划分对主元的选择。基本的快速排序选取第一个元素作为主元。这样在数组已经有序的情况下,每次划分将得到最坏的结果。一种比较常见的优化方法是随机化算法,即随机选取一个元素作为主元。这种情况下虽然最坏情况仍然是O(n^2),但最坏情况不再依赖于输入数据,而是由于随机函数取值不佳。实际上,随机化快速排序得到理论最坏情况的可能性仅为1/(2^n)。所以随机化快速排序可以对于绝大多数输入数据达到O(nlogn)的期望时间复杂度。一位前辈做出了一个精辟的总结:“随机化快速排序可以满足一个人一辈子的人品需求。”
随机化快速排序的唯一缺点在于,一旦输入数据中有很多的相同数据,随机化的效果将直接减弱。对于极限情况,即对于n个相同的数排序,随机化快速排序的时间复杂度将毫无疑问的降低到O(n^2)。解决方法是用一种方法进行扫描,使没有交换的情况下主元保留在原位置。
综合来说快速排序速度最快,时间复杂度最小。

Csdn user default icon
上传中...
上传图片
插入图片