为什么我写的快排比堆排序要慢得多?

C语言 码拜 10年前 (2015-05-11) 1478次浏览 0个评论

先上代码

void __quick_sort(int *p, int left, int right) {
  int pivot, pivot_index = left, i;
  
  swap(p, (left + right) / 2, right);
  pivot = p[right];

  for (i = left; i < right; i++) {
    if (p[i] >= pivot) {
      swap(p, i, pivot_index);
      pivot_index++;
    }
  }

  swap(p, pivot_index, right);

  if (left < pivot_index - 1)
    __quick_sort(p, left, pivot_index - 1);

  if (right > pivot_index + 1)
    __quick_sort(p, pivot_index + 1, right);
}

照着wikipedia上的pseudocode写的,测试通过,不过速度慢得很。
1000000个int,这个快排花了580ms,堆排序只用了360ms。
5000000个int,这个直接超过10s了,堆排序只用了2.5s不到。

排序的数是通过rand()生成的随机数,按理说这样的情况快排应该比堆排序要快才对啊?
难道我代码太渣拉低的效率?

都是用release版本测试的吗?

http://www.microsoft.com/visualstudio/chs/downloads#d-2010-express
点开Visual C++ 2010 Express下面的语言选‘简体中文’,再点立即安装

再参考C:\Program Files\Microsoft Visual Studio 10.0\VC\crt\src\qsort.c

10分
交换太多

字数补丁

20分
没看出来这个是快排,感觉你这个复杂度为O(n^2)
因为你一个for,再加了一个递归

感觉像是变形的冒泡~~~~

排序复杂度是lgn*n   

你这个方法说的不好听的  比2个for还烂

如果设计到数据查找的话,  最好还是用红黑树  每次插入最多做3次旋转即可,当然你这种已经存在大批量的数据的画,最快的还是快排
但是如果是频繁性的插入和查找的话还是应该用rbtree

10分
应该是数据分布不佳所致,一般数组小到一个程度转成插入排序,递归过深转为堆排,不要全程都是快排…
for那里。。。是从left到right遍历一次,相当于每次递归,你都要遍历一次,当然你这个有点像动态规划,交换次数可能比插入要少一点

要是序列稍微特殊一点,你这个算法就直接是O(N^2)了


CodeBye 版权所有丨如未注明 , 均为原创丨本网站采用BY-NC-SA协议进行授权 , 转载请注明为什么我写的快排比堆排序要慢得多?
喜欢 (0)
[1034331897@qq.com]
分享 (0)

文章评论已关闭!