為什麼在平均情況下快速排序比堆排序要優秀？

01-04

堆排序是漸進最優的比較排序演算法，達到了O(nlgn)這一下界，而快排有一定的可能性會產生最壞劃分，時間複雜度可能為O(n^2)，那為什麼快排在實際使用中通常優於堆排序？

樓上幾位說的不全，補充一下，堆排比較的幾乎都不是相鄰元素，對cache極不友好，這才是很少被採用的原因。

數學上的時間複雜度不代表實際運行時的情況

選擇排序、冒泡排序、插入排序，時間複雜度都是n*n，但是實際排序性能差別很大，為什麼？

差不多一回事

雖然qsort會n^2（其實有穩定的nlgn的版本），但這畢竟很少出現。hsort大多數情況下比較次數都多於qsort，儘管大家都是nlgn。那就讓倒霉蛋倒霉好了，大多數情況下快才是硬道理。

對於這個問題，我們主要可以從工作機理、原理分析以及複雜度比較三個角度去理解。

1 工作機理

設有任意一數組， C = [x1, x2, x3, …, Xn],

目標：將其從大到小進行排序；就快排和堆排兩個演算法的過程作出如下分析：

快速排序過程：

S1. 在數組中定義兩個指針 , p1, p2; 指針p1是從左向右，p2是從右向左。

S2. 取數組的第一個元素作為基準（理論上可以取任意一個），利用上述兩個指針找出比基準小的放在左邊，比基準大的放在右邊。

S3. 在第二步中調整完後，基準值會將原數組分成三部分，[比基準小的數]，[基準], [比基準大的數]

S4. 把S3中的 [比基準小的數], [比基準大的數] 代入S2 ;

堆排序過程：

S1. 初始化大頂堆；（該結構上是一顆完全二叉樹，該過程又叫構造堆過程。）

S2. 將最後一個元素與第一個元素互換；

S3. 重新調整至大頂堆，代入S1；

2 原理分析

（1）快速排序原理

其實就是通過不斷產生新的基準值，將原數組不斷地劃分成兩部分，然後進行大小調整。這樣做的原因是因為它在迭代過程中會產生一個不可控的序列，就是[比基準小的數], [比基準大的數]。我們只知道這兩個子數組裡面的元素比基準大或小，實質上該數組內部元素之間的大小關係我們不清楚，但是該演算法告訴我們可以通過不斷選取新的基準將數組劃分，可以使得這些「不可控的序列」逐漸變小直至消失，此時數組已經排好序，這就是快速排序要做的事情。

（2）堆排序原理

其實就是利用了大頂堆的性質，而實質上它又同時是一顆完全二叉樹。大頂堆的層級大小性質可以幫助我們控制部分數據的大小關係，完全二叉樹的順序儲存性質可以幫助我們把數據按一定大小關係排列起來。大頂堆告訴我們上一層的數據比下一層的數據大，但我們並不清楚每一層內部元素之間的大小關係，我們只能通過不斷調整堆，讓它自身不斷生成大頂堆，這樣會使每一層內部元素的大小產生調整，調整範圍也會越來越小，直至排序完畢，這就是堆排序要做的事情。

3 時間複雜度比較分析

上面大多都是陳鋪序述，熟悉演算法的朋友可以跳過。下面我們聚焦於兩個排序演算法之間的迭代過程中的一些小細節分析：

(1) 在快排的迭代過程中，我們所處理的 [比基準大的數]，[比基準小的數] 序列中，在進行兩個數之間大小比較時，在該局部範圍內，產生「大於」或者「小於」的可能性是一樣的。這意味著每比較一次必然會產生一次有意義的比較結果，會縮減接下來迭代的掃描工作量。

(2) 我們再來看看堆排序。在每一次進行重新堆調整的時候，我們在迭代時其實就已經知道，上一層的結點值一定是比下面大的。為了打亂堆結構把最後一個元素與頂堆互換時，此時我們也已經知道，互換後的元素是一定比下一層的數要小的。而在迭代時為了調整堆我們還是要進行一次已經知道結果的比較，這無疑是沒有什麼價值的，也就是產生了一次沒有意義的比較，對接下來的迭代工作量並沒有任何進展。

由上述不難看出，兩種排序方式都是採用了分治的思想，注意到該兩種演算法在迭代實現時，大體上都分成了兩條掃描路線：

A. 快速排序：

一是基於基準值調整大小時，對整個數組各項元素的掃描，該部分時間複雜度分N.

二是不斷產生新的基準值對數組進行劃分所產生的迭代次數，該部分時間複雜度為log(n).

(log(n)的由來：原數組不斷二分會產生的序列為n, n/2, n/4, …, n/2^k, 其中k的值就是需要迭代的次數，而n/2^k最終會收斂於1，亦即n/2^k=1時, n=2^k, log轉換: log(n) = k)

B. 堆排序：

一是在產生頂堆時對各個結點數之間的比較，會涉及到整個數組元素的掃描，該部分時間複雜度為n.

二是在調整堆的時候，對非葉子節點的掃描，該部分時間複雜度為log(n);

兩者平均時間複雜度均為o(nlog(n))。

對於快速排序，當數組的各項元素均相等，又或者是每一次迭代時選到的基準值恰恰是數組裡的最值，此時的快排時間複雜度就為o(n^2). 因為此時每一次迭代劃分數組所發生的比較都是無效比較。而這樣的情況發生的概率為 1 / (n * (n/2) * (n/4) ...(n/2^k)), 這是非常小的概率事件了。

而對於堆排序，礙於堆的特性，在迭代時所產生的無效比較概率是相對較大甚至為100%。 因此，在實際使用中，快速排序的使用常優於堆排序。

本次作答如有錯漏或不同見解，歡迎指出。

參考劉未鵬的數學之美番外篇：快排為什麼那樣快，

堆排序中的每次比較對問題集的劃分沒有快排效率高，平均下來則需要更多比較次數來找到最後結果，雖然複雜度是一樣的。

常數低。

很多工業庫中的排序演算法都是混合排序的，根據數據的情況和規模大小採用不同的排序方法，並把它們組合起來。

好久沒研究演算法了，坐等大大們提供細節。@vczh

對了，一定得吐槽一下，.NET 3和4里C#的不穩定排序演算法內部的策略不一樣了，導致當年做Visualization的時候因為結果突然變化折騰了好久。。。