universe-xy 2015-07-09 08:01 采纳率: 0%
浏览 3646

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

#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条回答

  • threenewbee 2015-07-09 08:09
    关注

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

    评论

报告相同问题?

悬赏问题

  • ¥15 关于#r语言#的问题:(svydesign)为什么在一个大的数据集中抽取了一个小数据集
  • ¥15 C++使用Gunplot
  • ¥15 这个电路是如何实现路灯控制器的,原理是什么,怎么求解灯亮起后熄灭的时间如图?
  • ¥15 matlab数字图像处理频率域滤波
  • ¥15 在abaqus做了二维正交切削模型,给刀具添加了超声振动条件后输出切削力为什么比普通切削增大这么多
  • ¥15 ELGamal和paillier计算效率谁快?
  • ¥15 file converter 转换格式失败 报错 Error marking filters as finished,如何解决?
  • ¥15 Arcgis相交分析无法绘制一个或多个图形
  • ¥15 关于#r语言#的问题:差异分析前数据准备,报错Error in data[, sampleName1] : subscript out of bounds请问怎么解决呀以下是全部代码:
  • ¥15 seatunnel-web使用SQL组件时候后台报错,无法找到表格