堆排序 歸并排序 快速排序
最壞時間 O(nlogn) O(nlogn) O(n^2)
最好時間 O(nlogn) O(nlogn) O(nlogn)
平均時間 O(nlogn) O(nlogn) O(nlogn)
輔助空間 O(1) O(n) O(logn)～O(n)
從時間復(fù)雜度看堆排序最好
有人說代碼實現(xiàn)后，數(shù)據(jù)量足夠大的時候，快速排序的時間確實是比堆排序短
解釋是，對于數(shù)組，快速排序每下一次尋址都是緊挨當(dāng)前地址的，而堆排序的下一次尋址和當(dāng)前地址的距離比較長。
1#
4種非平方級的排序：
希爾排序，堆排序，歸并排序，快速排序
我測試的平均排序時間：數(shù)據(jù)是隨機整數(shù)，時間單位是秒
數(shù)據(jù)規(guī)模 快速排序 歸并排序 希爾排序 堆排序
1000萬 0.75 1.22 1.77 3.57
5000萬 3.78 6.29 9.48 26.54
1億 7.65 13.06 18.79 61.31
堆排序是最差的。
這是算法硬傷，沒辦法的。因為每次取一個最大值和堆底部的數(shù)據(jù)（記為X）交換，重新篩選堆，把堆頂?shù)腦調(diào)整到位，有很大可能是依舊調(diào)整到堆的底部（堆的底部X顯然是比較小的數(shù)，才會在底部），然后再次和堆頂最大值交換，再調(diào)整下來。
從上面看出，堆排序做了許多無用功。
至于快速排序為啥比歸并排序快，我說不清楚。
2#
算法復(fù)雜度一樣只是說明隨著數(shù)據(jù)量的增加，算法時間代價增長的趨勢相同，并不是執(zhí)行的時間就一樣，這里面有很多常量參數(shù)的差別，即使是同樣的算法，不同的人寫的代碼，不同的應(yīng)用場景下執(zhí)行時間也可能差別很大。
快排的最壞時間雖然復(fù)雜度高，但是在統(tǒng)計意義上，這種數(shù)據(jù)出現(xiàn)的概率極小，而堆排序過程里的交換跟快排過程里的交換雖然都是常量時間，但是常量時間差很多。
3#
請問你的快快速排序是怎么寫的，我寫的快速排序，當(dāng)測試數(shù)組大于5000的時候就棧溢出了。
其他的幾個排序都對著，不過他們呢沒有用棧。
這是快速排序的代碼，win7 32位，vs2010.
1 int FindPos(double *p,int low,int high) 2 { 3 double val = p[low]; 4 while (low<high) 5 { 6 while(low<high&&p[high]>=val) 7 high--; 8 p[low]=p[high]; 9 while(low<high&&p[low]<val)10 low++;11 p[high]=p[low];12 }13 p[low]=val;14 return low;15 }16 void QuickSort(double *a,int low,int high)17 {18 if (!a||high<low)19 return;20 21 if (low<high)22 {23 int pos=FindPos(a,low,high);24 QuickSort(a,low,pos-1);25 QuickSort(a,pos+1,high);26 }27 }
……
7#
誰說的快排好?。课乙话愣加枚训?，我認(rèn)為堆好。
這個哪有譜啊，考察使用環(huán)境啊。不是只有時間代價一種衡量標(biāo)準(zhǔn)的，還有空間代價，LZ也有過棧溢出的經(jīng)歷，那不就是空間代價過高了嘛。改成別的辦法還是避免不了空間代價。LZ自己不是也已經(jīng)把空間待見列出來了嘛。
……
11#
我自己按照堆排序的算法思想實現(xiàn)了堆排序，寫完后對照網(wǎng)上的代碼，代碼幾乎是差不多的。
至于為何堆排序效率比希爾排序慢很多，我在上面帖子已經(jīng)說了，是堆排序的算法缺陷造成無用功太多。（我把堆排序看成是高級排序中的冒泡排序，冒泡也是兩兩交換做了太多無用功所以最慢。）
貼下我實現(xiàn)的希爾排序和堆排序，你可以自己去運行比較。
1 template <typename T> 2 void ShellSort(T arr[], int n) //希爾排序就是增量逐步縮小的直接插入排序 3 { //這里采用黃金分割的比例逐次減小增量 4 int gap = n * 0.382 + 0.5; //所以代碼和直接插入排序非常像。區(qū)別就是把增量1換成gap 5 int i, j; 6 T temp; 7 while (gap > 0) 8 { 9 for (i = gap; i < n; i++)10 {11 temp = arr[i];12 for (j = i - gap; j >= 0; j -= gap)13 {14 if (temp < arr[j])15 arr[j + gap] = arr[j];16 else17 break;18 }19 arr[j + gap] = temp;20 }21 gap = gap * 0.382 + 0.5;22 }23 }
1 template <typename T> 2 void HeapSort(T arr[], int n) 3 { 4 for (int i = n / 2 - 1; i >= 0; i--) //建立最大堆，從最后一個非葉節(jié)點開始 5 MaxHeapify(arr, n, i); //對于N規(guī)模的堆（0，n-1), n/2-1是最后一個非葉節(jié)點 6 7 T temp; 8 for (int i = n - 1; i > 0; i--) 9 {10 temp = arr[i]; //每次取堆頂數(shù)據(jù)和堆底部數(shù)據(jù)交換11 arr[i] = arr[0]; //并逐步縮小堆的大小12 arr[0] = temp;13 MaxHeapify(arr, i, 0); //重新篩選堆14 }15 }16 17 18 template <typename T>19 void MaxHeapify(T arr[], int n, int i)20 {21 T temp, max_data;22 int pos = i;23 int left = pos * 2 + 1;24 int right = left + 1;25 int max_pos;26 temp = arr[pos];27 28 while (left < n) //至少有左子樹29 {30 //取左右子樹的最大值31 max_data = arr[left];32 max_pos = left;33 if (right < n) //左右子樹均有34 if (arr[right] > arr[left])35 {36 max_data = arr[right];37 max_pos = right;38 }39 40 if (temp < max_data) //節(jié)點比左右子樹最大值小，繼續(xù)向下調(diào)整41 {42 arr[pos] = max_data;43 pos = max_pos;44 left = pos * 2 + 1;45 right = left + 1;46 }47 else48 break;49 }50 arr[pos] = temp; //回填51 }
12#
Mark一下, 有時間好好做一些實驗，給出具體結(jié)果。
這里先說說的我的看法，希望實驗?zāi)苤С治业念A(yù)測。
我認(rèn)為，
1. 快排的時間復(fù)雜度是不穩(wěn)定的，在最快情況下比歸并排序慢的多。
2. 當(dāng)數(shù)據(jù)量大時，充分優(yōu)化的歸并排序可比快速排序更快。其原因有
1）. 歸并排序?qū)?nèi)存的訪問是嚴(yán)格的順序方式（3個2個源數(shù)組，1個目標(biāo)數(shù)組，都是順序放分），故cache的命中率比快排更高，從這點上，相同的內(nèi)存讀寫操作，歸并優(yōu)于快排，當(dāng)數(shù)組占用的空間大大超過cache的大小，則這一優(yōu)勢將更加明顯。
2）普通寫法的歸并排序有2個缺點，如果改進(jìn)，則可以提速。如果你的實驗是基于最普通的版本，得到的結(jié)果是快排優(yōu)于歸并，而優(yōu)化的歸并排序的版本，其性能則可能反超快排。
2.1） 歸并排序不是In place.需要將結(jié)果存儲到臨時緩沖區(qū)，然后在復(fù)制回來，這個過程可以優(yōu)化掉。使用乒乓做法，在第i級歸并過程，從buff1 歸并到buff2,在i+1級歸并過程，從buff2復(fù)制到buff1。
2.2） 2路歸并排序的核心動作是比較2個對列的頭元素那個更大，其比較結(jié)果是隨機的，2個分支機會均等，CPU的分支預(yù)測算法不起作用，當(dāng)預(yù)測失敗，可大大降低程序性能，如果消除這個分支，可明顯提高程序性能。
13#
樓主知道標(biāo)準(zhǔn)庫的sort是怎么實現(xiàn)的么？ 先快排，遞歸深度超過一個閥值就改成堆排，然后對最后的幾個進(jìn)行插入排序。 //233系統(tǒng)真機智
14#
1.快排的時間復(fù)雜度確實不穩(wěn)定，極端情況是O(n^2)，但是平攤下來是T(n*lg(n))，而歸并是嚴(yán)格的O(n*log(n))。
2.快速排序比歸并排序快。其原因有
1）快排對內(nèi)存的訪問是順序方式（包括逆序），只有兩個目標(biāo)而且是同一個數(shù)組，故cache的命中率不會比歸并低。特別是數(shù)組空間接近于cache大小時，這一優(yōu)勢將更加明顯。
2）快排的內(nèi)存寫操作次數(shù)平攤下來是T(n*lg(n)/2)，而歸并的內(nèi)存寫操作次數(shù)是嚴(yán)格的O(n*log(n))，由于內(nèi)存寫操作開銷比較大，所以對于隨機數(shù)據(jù)快排優(yōu)于歸并。
……
16#
同學(xué)們，這些算法都有標(biāo)準(zhǔn)的開源程序。
自己寫程序?qū)斫馑惴ǖ拇_有好處。
但是如果用于得到一般性的比較結(jié)果，那是靠不住的。
原帖到此終結(jié)；
文自：http://bbs.csdn.net/topics/390554511
