快速排序和它在工程實踐中的應用

前言

對於排序來說，雖然快速排序是一種在最壞情況下時間複雜度為平方級別（theta(n^2)）的排序演算法，但它卻是在實際的排序應用中最好的選擇，因為它的平均性能非常好，它的期望時間複雜度為 theta(nlgn)，而且 theta(nlgn) 中隱含的常數因子非常小。

為什麼說快速排序在實際的應用中是最好的選擇呢？因為在工程實踐中，我們通過各種手段去改進它在最壞情況下的時間複雜度，使得它在大概率情況下都能獲得它的期望時間複雜度。

快速排序的基本實現

下面我們直接來看一下快速排序的提出者 Hoare 的原始版本的實現，依據《演算法導論》寫的：

下面是實現：

可以看到，當 partition 結束時，它返回的值 j 滿足 left

當 partition 結束時，a[left… j] 區間中的每一個元素都小於或等於 a[j + 1…right] 區間中的元素。

主元是存在於區間 a[left…j] 或 a[j + 1, rright] 中的。

下面又是另一種實現：

原理：兩跟指針分別從數組的一頭一尾出發，右指針直到碰到比主元（pivot）大的才停下來，左指針直到碰到比主元小的才停下來，如果左指針的位置比右指針的位置要小，才交換兩個指針所指的值。直到左指針的位置比右指針的位置要大或者左指針到達數組的右邊或者右指針到達數組的左邊，循環跳出，並交換此時主元所在位置的值和右指針所指的值。

還有一個《演算法導論》上的實現：

paratition 維護了4個區域。在 a[p]~a[i] 區間內的所有值都小於等於 pivot，在 a[i + 1]~a[j - 1] 區間內的所有值都大於 pivot，a[start] = pivot，子數組 a[j]~a[end - 1] 中的值可能屬於前面的任何一種情況。

快速排序用了分治的思想，通過遞歸調用快速排序，將劃分的數組進行排序。

快速排序的性能

快速排序最好的時間複雜度為 theta(nlgn)，最差的時間複雜度達到了平方級別。

最差的情況出現在劃分的不平衡上。假設每次在劃分時，產生的兩個子問題分別包含了 n - 1 個元素和 0 個元素。那麼在這種情況下時間複雜度就達到 theta(n^2)。相關的數學證明《演算法導論》第三版上有，這裡就不給出來了。

在可能的最平衡的劃分中，即兩個子問題的規模都不大於 n/2，此時的性能會非常好，也就是 theta(nlgn)。

在劃分上，任何一種常數比例的劃分都會產生深度為 theta(lgn) 的遞歸樹，其中每一層的時間代價都是 O(n)。因此，只要劃分是常數比例的，演算法的運行時間總是 O(nlgn)。

這上面的代碼中，為了方便並沒有隨機地打亂數組元素的順序。但是在實際中，這個是很重要的。引入隨機性，我們可以對所有的輸入都能獲得較好的期望性能。

演算法改進

切換到插入排序

當數組裡的元素基本有序的時候，插入排序的速度會很快。對於小數組，快速排序比插入排序慢，因為快速排序在小數組裡也會遞歸調用自身。基於此，在數組基本有序或是小數組時，應該切換到插入排序。那這個小到底是怎樣衡量的呢？這個會在後面說到。

三數取中劃分

在選取主元時，我們通常會取數組中的第一個元素或者最後一個元素。這樣就可能會導致劃分的不平衡。所以當主元是隨機選取的時候，對數組的劃分會比較平衡。但是我們有更好的辦法去更細緻地選擇作為主元的元素，而不是隨機選取。人們發現，從數組中隨機選取出３個元素並用它們中的中位數作為主元效果最好。

針對重複元素值的三向劃分快速排序(或叫三向切分的快速排序)

當一個數組的含有大量重複元素的時候，特別是當劃分出的子數組全是相同的值時，快速排序依然會繼續劃分，這就浪費了很多時間。從而也就有很大的改進空間。下面是實現：

它從左到右遍曆數組一次，維護一個指針 lo 使得 a[left…lo - 1] 中的元素都小於 pivot，一個指針 hi 使得 a[hi + 1…right] 中的元素都大於 pivot，一個指針 i 使得 a[lo…i - 1] 中的元素都等於 pivot，a[i…hi] 中的元素還未確定。

三向字元串快速排序

待補充。。。

Java 中的排序庫函數

在寫 Java 程序時，我們經常會使用 Arrays 類裡面的 sort 函數進行元素的排序。那麼究竟這個 sort 函數是怎麼實現的呢？現在就讓我們深入到源代碼里看看。首先調用 Arrays 類裡面的 sort 函數時，底層是這樣的：

咦？？？這個 DualPivotQuicksort 究竟是個什麼東西？從名字就可以略知一二：雙樞軸快速排序。所以，它下面的 sort 方法便是雙樞軸快速排序的實現。Dual-Pivot Quicksort algorithm 是由 Vladimir Yaroslavskiy 發明的，我特意去找了他所寫的關於這個演算法的論文，覺得還是很有意思的。論文 在此 ，可以點擊進行下載。那下面我們來詳細看一下論文的內容。

Dual-Pivot Quicksort algorithm

Dual-Pivot Quicksort algorithm 簡介

相比經典的快速排序演算法，Dual-Pivot Quicksort 使用了兩個 pivot 元素。Vladimir Yaroslavskiy 在論文里說 Dual-Pivot Quicksort 比經典的快速排序更快更高效，特別是在大數組上。這個演算法經過了大量的數據驗證，所以說挺可靠的了。所以他也說 Dual-Pivot Quicksort algorithm 能被推薦寫到下一代 JDK 的發行版（這裡也就是 JDK 7）裡面。這裡我用的是 JDK 8。

在 Dual-Pivot Quicksort algorithm 中，使用兩個 pivot 把數組 T[] a，T 是基本數據類型，劃分成3個部分，同時還有3個指針，分別是 L、K、G，還有兩個指向數組中第一個元素和最後一個元素的指針，分別是 left 和 right。不妨命名這兩個 pivot 為 P1 和 P2。下面是一個示意圖：

下面來說一個演算法的執行步驟：

首先它先判斷數組的元素個數，如果小於2（但 JDK 源碼定義的 INSERTION_SORT_THRESHOLD 的值為47），則使用插入排序。這個 INSERTION_SORT_THRESHOLD 是一個私有的常量值，表示使用插入排序的閾值，如果數組的元素小於27（對於 JDK 來說是47）個，則用插入排序。

選擇兩個 pivot 元素，P1 和 P2。例如，我們可以取 a[left] 為 P1，a[right] 為 P2。

P1 必須要比 P2 小！如果不是的話就比較它們的大小，然後進行一個交換。所以，現在就可以劃分成這些部分了：

part I 為區間 a[left + 1…L - 1]，這個部分的元素全部都小於 P1，

part II 為區間 a[L …K - 1]，這個部分的元素全部都大於等於 P1 並 小於等於 P2，

part III 為區間 a[G + 1…right - 1]，這個部分的元素全部都大於 P2，

part IV 為區間 a[K…G]，這個部分包含這個數組剩餘的元素。

接下來，來自 part IV 的元素 a[K] 將與 P1 和 P2進行大小比較，比較之後將它放置到對應的部分，part I 或 part II 或 part III。

指針 L，K 和 G 在相應的方向上移動。

當 K

當 part IV 的所有元素都找到它們的歸屬之後，將 P1 與 part I 的最後一個元素進行交換，這樣 P1 就納入了 part I 裡面了；將 P2 與 part III 的第一個元素進行交換，這樣 P2 也納入了 part III。

運用分治法，part I、part II、part III 將遞歸地重複步驟 1 - 7。

Vladimir Yaroslavskiy 證明了 Dual-Pivot Quicksort algorithm 的平均比較次數為 2nln(n)，平均元素交換次數為 0.8nln(n)，而經典的快速排序相應的次數為 2nln(n) 和 1nln(n)。

演算法實現

測試程序：

3億個1000000以內的整數排序，測試發現，Arrays.sort 比原始版本的 Dual-Pivot Quicksort 快了5倍多（本機 i5 + 8g），可見寫進 JDK 源碼里的 Dual-Pivot Quicksort 做了更多更複雜的優化。比如說使用插入排序時，JDK 源碼裡面使用了傳統的插入排序和 pair insertion sort，詳細的可以去看看源碼。除了插入排序，還會使用到歸併排序，因為歸併排序的平均時間複雜度也是 theta(nlgn)，這這是一個非常好的性能。除了這些之外，對於 byte、short 和 char 數組，對於一個特定的閾值，會使用計數排序，它是一種穩定的線性時間排序演算法，一種非比較的排序演算法。一般來講，基於比較的排序突破不了下界 theta(nlgn)。

總結

可以看到，能在工程實踐中使用的排序演算法，肯定是考慮到了很多種情況，融合了各種排序演算法的優點，以達到面對各種輸入都能得到比較好的性能。其實，在 C++ 裡面的 std::sort 方法里，也是基於快速排序設計的一種排序演算法，融合插入排序、堆排序（在遞歸深度超過一定值的時候）和快速排序，這個排序我們叫它 introsort (內省排序)，這個有機會再研究一下。

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！