#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命中率的原因
哪位大神可以解释一下