快排、堆排对于随机数据的效率测试

放假期间无所事事，决定回顾一下快速排序和堆排序。
自从转C后，快排都用qsort解决，去年参加CCF培训的时候有些选手说stdlib里面的qsort效率低，自己写更好。
堆排序实际并不常用，除非用于一些变动频繁的数据，例如dijstra算法中的最小堆优化。
堆排和快排的时间复杂度都是O(nlogn)，但这并不代表它们的实际效率是相同的，于是就有了下面的测试。

先介绍下环境：CPU~Dual core Intel Core i3 CPU M 370 (-HT-MCP-) clocked at 933.000 Mhz Kernel~3.0.0-17-generic x86_64 Up~4:08 Mem~674.2/3760.7MB HDD~320.1GB(44.1% used) Procs~181 Client~Shell inxi~1.7.7
首先，随机生成10000000个数字，存到rand.txt

然后，用下面的代码测试：

C语言: 高亮代码由发芽网提供

001 #include
002 #include
003 #include
004 #include
005 #define MAXN 10000000
006
007 long num[MAXN];
008 long bak[MAXN];
009 long heapsize;
010
011 long lc(long k)
012 {
013     return 2 * k + 1;
014 }
015
016 long rc(long k)
017 {
018     return 2 * k + 2;
019 }
020
021 long p(long k)
022 {
023     return (k - 1) >> 1;
024 }
025
026 void read()
027 {
028     long i;
029     for(i = 0;i < MAXN;i ++)
030         scanf("%ld",&num[i]);
031 }
032
033 void pt()
034 {
035     long i;
036     for(i = 0;i < MAXN;i ++)
037         printf("%ld\n",num[i]);
038 }
039
040 int cmp(const void *a,const void *b)
041 {
042     return *(long *)a > *(long *)b;
043 }
044
045 void quicksort(long l,long r)
046 {
047     if(l < r)
048     {
049     long mid,key,tmp,i,j;
050     mid = (l + r) >> 1;
051     key = num[mid];num[mid] = num[r];num[r] = key;
052     for(i = j = l;i < r;i ++)
053     {
054         if(num[i] < key)
055         {
056             tmp = num[i];
057             num[i] = num[j];
058             num[j] = tmp;
059             j ++;
060         }
061     }
062     num[r] = num[j];
063     num[j] = key;
064     quicksort(l,j - 1);
065     quicksort(j + 1,r);
066     }
067 }
068
069 void quicksort_rand(long l,long r)
070 {
071     if(l < r)
072     {
073     long mid,key,tmp,i,j;
074     mid = rand() % (r - l) + l;
075     key = num[mid];num[mid] = num[r];num[r] = key;
076     for(i = j = l;i < r;i ++)
077     {
078         if(num[i] < key)
079         {
080             tmp = num[i];
081             num[i] = num[j];
082             num[j] = tmp;
083             j ++;
084         }
085     }
086     num[r] = num[j];
087     num[j] = key;
088     quicksort(l,j - 1);
089     quicksort(j + 1,r);
090     }
091 }
092
093 void heapfy(int k)
094 {
095     long min,tmp;
096     min = k;
097     if(lc(k) < heapsize && num[lc(k)] < num[min])    min = lc(k);
098     if(rc(k) < heapsize && num[rc(k)] < num[min])    min = rc(k);
099     if(min != k)
100     {
101         tmp = num[min];
102         num[min] = num[k];
103         num[k] = tmp;
104         heapfy(min);
105     }
106 }
107
108 long extract_min()
109 {
110     long min = num[0];
111     num[0] = num[--heapsize];
112     heapfy(0);
113     return min;
114 }
115
116 void heapsort()
117 {
118     long i;
119     for(i = MAXN / 2;i >= 0;i --)
120         heapfy(i);
121     while(heapsize >= 1)
122     {
123         i = extract_min();
124         //printf("%ld\n",i);
125     }
126 }
127
128 void create()
129 {
130     FILE *out;
131     out = fopen("rand.txt","w");
132     long i;
133     srand(time(NULL));
134     for(i = 0;i < MAXN;i ++)
135         fprintf(out,"%d\n",rand());
136     exit(0);
137 }
138
139 int main()
140 {
141     clock_t start,end;
142     //create();
143     read();
144     memcpy(bak,num,sizeof(num));
145     start = clock();
146     qsort(num,MAXN,sizeof(long),cmp);
147     end = clock();
148     //pt();
149     fprintf(stderr,"Biult-in qsort:%f\n",(double)(end - start) / CLOCKS_PER_SEC);
150
151     memcpy(num,bak,sizeof(num));
152     start = clock();
153     quicksort(0,MAXN - 1);
154     end = clock();
155     fprintf(stderr,"My QuickSort:%f\n",(double)(end - start) / CLOCKS_PER_SEC);
156     //pt();
157    
158     memcpy(num,bak,sizeof(num));
159     start = clock();
160     quicksort_rand(0,MAXN - 1);
161     end = clock();
162     fprintf(stderr,"My QuickSort(Rand):%f\n",(double)(end - start) / CLOCKS_PER_SEC);
163     //pt();
164    
165     memcpy(num,bak,sizeof(num));
166     start = clock();
167     heapsize = MAXN;
168     heapsort();
169     end = clock();
170     fprintf(stderr,"HeapSort:%f\n",(double)(end - start) / CLOCKS_PER_SEC);
171     return 0;
172 }

当MAXN定义为1000000时，输出如下：

Biult-in qsort:0.250000
My QuickSort:0.240000
My QuickSort(Rand):0.230000
HeapSort:0.830000

当MAXN达到10000000时：
Biult-in qsort:3.010000
My QuickSort:2.640000
My QuickSort(Rand):2.640000
HeapSort:13.430000

整体上，可以看出，对于随机数据，单次排序，快排的表现明显优于推排序。个人推测原因是堆排序存在建堆、弹出小元素和维护堆三个过程，因此耗时会多一些。

对于快速排序，qsort使用方便，效率略低。自己写的随机化快排速度最快。不过三者差别并不明显，本人还是推荐用stdlib内置的qsort——简单，安全。