在計算機科學中，通常認為最好的排序算法是託尼·霍爾(Tony Hoare)發明的快速排序(Quicksort)算法。這位託尼·霍爾還因此獲得了爵士頭銜，由此可見該算法的重要性和精妙程度。 

託尼·霍爾在前蘇聯莫斯科國立大學做訪問學生時，為了解決俄文排序問題，他首先嚐試了插入排序，但是由於不滿插入排序的效率，他想出了快速排序的方法。大神的世界就是自己給自己發明工具。高德納為了寫書而開發了印刷行業最好的排版軟件，牛頓為了解決加速度等問題而發明了微積分。但是霍爾當時沒有掌握支持遞歸的編程語言，所以一直沒有實現該算法。直到後來回到英國，學習了ALGOL(支持遞歸)語言，他才把自己的想法付諸實踐，而且發現竟然比希爾排序還要快。

也許有的讀寫還想追問，有沒有比快速排序更快的方法了呢？沒有了，這個可以從數學角度證明。如果有人非要說有更快的方式，那他就是在挑戰數學，這和相信永動機的人挑戰熱力學定律沒有本質上的區別。

快速排序，充分利用了分治(divide and conquer)的思想，其核心思想就是少做無用功。

基本思想

2.1 快速排序的一般過程

快速排序的一般過程是，隨機選取數組中的一個值，作為比較標準，一般稱之為樞值(Pivot)。然後把整個數組中小於樞值的數據分到一個組，把大於樞值的數據分到另一個組，等於樞值的數據分到哪個組都可以。分成兩組後，自然不會用其他排序對小數組進行排序，而是重複以上的步驟，把小的數組再細分。這樣整個數組就由1個數組變成2個數組，再變成4個數組，再變成8個數組，到最後分無可分，簡單比較一下，整個數組就變得有序了。

簡單描述一下：

1. 選擇樞值。也就是選擇一個數據作為標杆。選擇樞值其實是最重要的一個步驟，比較推薦的方法是，選擇數組中第一個、中間以及最後一個數據中的中值。
2. 分組操作。把大於樞值的數據放到樞值右邊，把小於樞值的數據放到左邊。與樞值相等的數據放到哪邊無所謂。
3. 遞歸。
   對左右兩邊的數據進行樞值選取和分組操作。遞歸的停止條件是細分數組數據個數為0或者1。

來看一張稍微複雜一點的圖，圖中陰影部分的數據就是各個階段的樞值。

From Wikipedia

樞值選取方式和分組操作是快速排序的核心，常見的有兩種方案，即Lomuto和Hoare分組方案。

2.2 Lomuto分組方案

最簡單也是最常見的分組方式是Lomuto分組方案，該方案直接選取最後一個元素作為樞值，該方案最明顯的缺點是，當一個數組已經是有序的或者數組所有數字相同，反而會出現最糟糕的排序情況，即複雜度為O(n²)。

不防看一下1、2、3、4、5這樣一個數組。使用該方案首先選擇5為樞值，則第一次分組後僅左邊有1、2、3、4這四個數字，而右邊沒有任何數字，第二次選擇4為樞值，結果還是一樣，這樣每次分組都只能使一個數字變得有序，效率自然就退化成O(n²)。

直接上偽碼：

2.3 Hoare分組方案

另一個方法則是Hoare的分組方案，通過一定的方法選擇一個樞值，一般選擇數組中間的值，不妨設數組A首尾元素的下標分別為lo和hi，則樞值

Pivot = A[(lo + hi) / 2]

當然，為了避免整數溢出問題，一般寫成

Pivot = A[lo + (hi - lo) / 2]

關於整數溢出有機會再說。其思想是從數組左右兩端開始，從左端向右側查找第一個大於等於樞值的數據，記錄下標為i，從右端向左側查找第一個小於等於樞值的數據，記錄下標為j，然後交換A[i]和A[j]。然後繼續如上操作，直到i大於等於j結束，這樣原來的數組就分成了兩個數組，左側的均小於樞值，右側均大於等於樞值，然後再對子數組重複如上的操作。

以數組4、5、3、2、1為例：

1. 選取3為樞值，找到左端數據4大於樞值，右端數據1小於樞值，交換數據得到1、5、3、2、4，
2. 繼續向內掃描數據，發現需要交換5和2，這樣得到1、2、3、4、5
3. 繼續對兩個子數組1、5和4、5進行如上操作，發現已經完成排序。

老規矩，上偽碼：

2.4 其他分組方案

此外，《算法導論》中還提到隨機化，也就是隨機的選擇樞值，可能你不信，很多排序算法都會用到隨機化這個概念，因為很多時候，隨機化帶來的結果往往意想不到的好。這裡暫不贅述，有機會單獨講一講。Sedgewick推薦一種選取樞值的方法被稱為三數取中(median-of-three)，即從數組第一個數據、正中間數據以及最後一個數據中選取中間值為樞值。三數取中的升級版本也被稱為ninther，不妨定義函數median-of-three (Mo3)：

Mo3(A) = median(A[1], A[n/2], A[n])

ninther(a) = median(Mo3(first ⅓ of a), Mo3(middle ⅓ of a), Mo3(final ⅓ of a))

即取數組前三分之一找出中值，然後取數組中間三分之一找出中值，再取數組最後三分之一找出中值，最後選擇這三個中值中的中值。

複雜度

3.1 時間複雜度

快速排序對於已經有序的數組或者所有數據都相等的數組排序的複雜度是O(n²)，這種情況有多種方法優化，比如，可以嘗試把數據分成3組，即大於樞值為一組，等於樞值為一組，小於樞值為一組，其原因很好理解，這裡就不贅述了。也可以評估數據的個數，對於較少的數據，完全不需要使用快速排序，可以直接使用選擇排序或者希爾排序。

快速排序的平均複雜度是O(n*log n)，除了快速排序還有歸併排序和堆排序的複雜度也是O(n*log n)，那為什麼一般都說快速排序是最快的排序算法呢？其實讀過我之前關於複雜度的文章的讀者應該都知道，對於複雜度為O(C*n*log n)的算法，其複雜度都是O(n*log n)，這裡的C為常數。快速排序之所以最快，主要是因為它的常數C比較小，在具體應用中，快速排序的表現也往往比較好的。

3.2 空間複雜度

快速排序的空間複雜度和具體的實現方式有關。Sedgewick描述的一種方案，針對就地(in-place)排序實現，首先通過遞歸對元素最少的分組進行排序，最多需要O(log n)的空間，然後使用尾部遞歸或者迭代的方式對另一部分分組數據排序，這就避免了把這部分排序操作添加到調用棧，也就是說，這樣可以限制調用棧的深度不會超過O(log n)，也就保證了空間複雜度為O(log n)。其他一些非就地(not-in-place)排序實現，空間複雜度則為O(n)。

其實也可以換個角度理解快速排序的空間複雜度。快速排序的遞歸過程可以用二叉樹來表示，則調用棧的層次和二叉樹的深度保持一致，那麼最好的情況樹的深度為O(log n)，即此時空間複雜度為O(log n)。而最壞的情況發生在二叉樹退化成單鏈，深度為O(n)，空間複雜度也就是O(n)了。

3.3 穩定性和實際表現

快速排序也是不穩定的排序算法。

實測一下算法表現，簡單看一下插入排序、希爾排序以及快速排序的效率，以10000個隨機數排序耗時為例：

很顯然，快速排序耗時僅有希爾排序的一半。想要獲取源碼，後臺回覆『快速排序』獲取源碼。

小結分析

快速排序的整體思想很簡單，就是先按照一定的標準（樞值），先把數據三六九等的分開，然後在小範圍內繼續三六九等的分下去，直到分無可分。也就是每個數據都找到自己的位置了。快速排序的空間複雜度遠大於希爾排序，這也再次說明了，在計算機科學中，到處都存在用空間換時間的權衡(trade-off)。

至於快速排序樞值的選擇，方法有無數種，表現也參差不齊。但是隻要遵從其核心思想，排序的速度就會有質的提升。從代碼實現角度看，快速排序的實現僅需10多行代碼，可見，好的東西往往是極其簡單的，如果你把一件事搞複雜了，不妨停下腳步，思考一下是不是做事的方法出了問題。

很多時候，做事其實也應該如此，要學會分而治之，把大的問題按照一定的標準無限細分下去，到最底層時，只需要做很少的事情就可以完成一個大目標。就像一個公司，不同人分到不同的崗位，然後各司其職，就可以創造一個偉大的公司。