问题描述

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

#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毫秒nn",duration);
free(src);
free(tem);
return 0;
}

                 快速排序（ms）   归并排序（ms）

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

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

解决方案

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

解决方案二：

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