堆排序和快排序，随更快？该怎么解决

堆排序和快排序，随更快？
我使用C++实现了快排序和堆排序，自己试验了一下，发现快排序比堆排序慢很多，不知道为什么。下面是我的代码：

C/C++ code

//quick sortint partition(int* arr,const int left,const int right){    int leIdx=left-1;    for(int i=left;i<=right-1;++i){        if(arr[i]<=arr[right]){            ++leIdx;            swap(arr[leIdx],arr[i]);        }    }    swap(arr[leIdx+1],arr[right]);    return leIdx+1;}void quickSort(int* arr,const int left,const int right){    if(left<right){        int index=partition(arr,left,right);        quickSort(arr,left,index-1);        quickSort(arr,index+1,right);    }}void quickSort(int* arr,const int len){    quickSort(arr,0,len-1);}

C/C++ code

//heap sortvoid heapDown(int* arr,const int idx,const int len){    if(idx>=static_cast<int>(len/2)){//该节点是叶子        return;    }    int maxSon=2*idx+1;//初始最大儿子是左儿子    if( maxSon+1<len && arr[maxSon+1]>arr[maxSon]){//如果右儿子存在，并且大于左儿子        ++maxSon;    }    if(arr[maxSon]>arr[idx]){        swap(arr[maxSon],arr[idx]);        heapDown(arr,maxSon,len);    }}void buildHeap(int* arr,const int len){    for(int i=static_cast<int>(len/2)-1;i>=0;--i){        heapDown(arr,i,len);    }}void heapSort(int* arr,const int len){    buildHeap(arr,len);    for(int i=len-1;i>=1;--i){        swap(arr[0],arr[i]);        heapDown(arr,0,i);            }}

C/C++ code

//main 函数#include "sort.h"#include <iostream>#include <string>#include <ctime>using namespace std;int* generateRandom(int len,const int low,const int high){    ::srand(time(NULL));    int* arr=new int[len];    for(int i=0;i<len;++i){        arr[i] = low+rand()%(high-low+1);    }    return arr;}void testSortFunction(const int* unsorted,int len,SortFunction sf,const string name){    int* arr=new int[len];    for(int i=0;i<len;++i){        arr[i]=unsorted[i];    }    clock_t start=clock();    sf(arr,len);//sort    clock_t end=clock();    cout<<name<<" Count "<<len<<" costs "<<(end-start)/(double)CLOCKS_PER_SEC<<" s"<<endl;    delete [] arr;}void main(int argc,char* argv[]){    const int N = 10000000;    int* unsorted = generateRandom(N,0,2000);    cout<<"Random Count: "<<N<<endl;    cout<<"******************************************************"<<endl;    testSortFunction(unsorted,N,quickSort,"Quick Sort");    testSortFunction(unsorted,N,heapSort,"Heap Sort");    cout<<"******************************************************"<<endl;    delete [] unsorted;    system("pause");}

测试结果：
快排序 53.5秒
堆排序 4.906秒

为什么快速排序比堆排序慢这么多，请哪位算法大侠告诉我原因？


[解决办法]
首先，楼主的“快排算法”根本就不是真正的快排算法，楼主自己可以在网上搜到真正的快排算法；
其次，优化的快排算法，其实是极难碰到完全退化成O(n^2)的情况，而且有些快排算法会考虑递归深度，如果深度大于阈值，就会调用堆排序进行处理。
[解决办法]
比较的话，用抽象的数学方式比较才有意义
因为同一个算法，实现的人不同，效率不一样，测试数据不一样，差别也大
一个人实现不同的算法也有差异，擅长的算法，实现的往往效率高些，
[解决办法]
小数据量排序，用冒泡，选择等排序比快排快

因为快排，堆栈比较费时。
[解决办法]
mark
[解决办法]
那是你的快速排序实现不好！！！经过良好设计的快速排序，一般情况下要比堆排序快2倍！！！其实，C/C++都无法体现它们两个的差别，想更深入比较，请看《The Art of Computer Programming》中对快速排序和堆排序的分析，那才是原子级别的比较。

想更好地实现快速排序，请参考： 

1.《Quicksort》,by C.A.R. Hoare.
2.《Introduction to Algorithms》,中文《算法导论》，By Thomas H. Cormen,Charles E. Leiserson,Ronald L. Rivest,Clifford Stein.
3.《The Art of Computer Programming》,Volum3.Sorting and Searching.
by Ronald E. Knuth. 
4.《Implementing quicksort programs》,by Robert Sedgewick. 
5.《Algoritms》,by Robert Sedgewick.
6.《Algorithms in C, Parts 1-4: Fundamentals, Data Structures, Sorting, Searching (3rd Edition) (Pts. 1-4)》.by Robert Sedgewick. 
7.《An Introduction to the Analysis of Algorithms》,by Robert Sedgewick. 

还有几篇Robert Sedgewick关于快速排序的论文，忘记了，你可以搜搜。。。。 

Robert Sedgewick是研究快速排序的集大成者，想很好的实现，他的文献不要错过。。。
[解决办法]
请问lz SortFunction 是怎么定义的？
[解决办法]
你还是重新看看排序算法吧~！
[解决办法]
做这种测试，你不能只生成一组数据，这样不可靠
你可以生成n组数据，求平均时间
即使是快排，也有不擅长的输入

查看更多 下一篇