# Quick Sort - 快速排序 核心：快排是一種采用分治思想的排序算法，大致分為三個步驟。 1. 定基準——首先隨機選擇一個元素最為基準 1. 劃分區——所有比基準小的元素置于基準左側，比基準大的元素置于右側 1. 遞歸調用——遞歸地調用此切分過程 ### out-in-place - 非原地快排 容易實現和理解的一個方法是采用遞歸，使用 Python 的 list comprehension 實現如下所示： ~~~ #!/usr/bin/env python def qsort1(alist): print(alist) if len(alist) <= 1: return alist else: pivot = alist[0] return qsort1([x for x in alist[1:] if x < pivot]) + \ [pivot] + \ qsort1([x for x in alist[1:] if x >= pivot]) unsortedArray = [6, 5, 3, 1, 8, 7, 2, 4] print(qsort1(unsortedArray)) ~~~ 輸出如下所示： ~~~ [6, 5, 3, 1, 8, 7, 2, 4] [5, 3, 1, 2, 4] [3, 1, 2, 4] [1, 2] [] [2] [4] [] [8, 7] [7] [] [1, 2, 3, 4, 5, 6, 7, 8] ~~~ 『遞歸 + 非原地排序』的實現雖然簡單易懂，但是如此一來『快速排序』便不再是最快的通用排序算法了，因為遞歸調用過程中非原地排序需要生成新數組，空間復雜度頗高。list comprehension 大法雖然好寫，但是用在『快速排序』算法上就不是那么可取了。 ### 復雜度分析 在最好情況下，快速排序的基準元素正好是整個數組的中位數，可以近似為二分，那么最好情況下遞歸的層數為 logn\log nlogn, 咋看一下每一層的元素個數都是 nnn, 那么空間復雜度為 O(n)O(n)O(n) 無疑了，不過這只答對了一半，從結論上來看是對的，但分析方法是錯的。 首先來看看什么叫空間復雜度——簡單來講可以認為是程序在運行過程中所占用的存儲空間大小。那么對于遞歸的 out-in-place 調用而言，排除函數調用等棧空間，**最好情況下，每往下遞歸調用一層，所需要的存儲空間是上一層中的一半。完成最底層的調用后即向上返回執行出棧操作，故并不需要保存每層所有元素的值。**所以需要的總的存儲空間就是∑i=0n2i=2n\sum _{i=0} ^{} \frac {n}{2^i} = 2n∑i=02in=2n 不是特別理解的可以結合下圖的非嚴格分析和上面 Python 的代碼，遞歸調用的第一層保存8個元素的值，那么第二層調用時實際需要保存的其實僅為4個元素，逐層往下遞歸，而不是自左向右保存每一層的所有元素。 那么在最壞情況下 out-in-place 需要耗費多少額外空間呢？最壞情況下第 iii 層需要 i?1i - 1i?1 次交換，故總的空間復雜度： ∑i=0n(n?i+1)=O(n2)\sum_{i=0}^n (n-i+1) = O(n^2)∑i=0n(n?i+1)=O(n2)  ### in-place - 原地快排 ### one index for partition 先來看一種簡單的 in-place 實現，仍然以`[6, 5, 3, 1, 8, 7, 2, 4]`為例，結合下圖進行分析。以下標 lll 和 uuu 表示數組待排序部分的下界(lower bound)和上界(upper bound)，下標 mmm 表示遍歷到數組第 iii 個元素時當前 partition 的索引，基準元素為 ttt, 即圖中的 target.  在遍歷到第 iii 個元素時，x[i]x[i]x[i] 有兩種可能，第一種是 x[i]≥tx[i] \geq tx[i]≥t, iii 自增往后遍歷；第二種是 x[i]<tx[i] < tx[i]<t, 此時需要將 x[i]x[i]x[i] 置于前半部分，比較簡單的實現為 `swap(x[++m], x[i])`. 直至 `i == u` 時劃分階段結束，分兩截遞歸進行快排。既然說到遞歸，就不得不提遞歸的終止條件，容易想到遞歸的終止步為 `l >= u`, 即索引相等或者交叉時退出。使用 Python 的實現如下所示： ### Python ~~~ #!/usr/bin/env python def qsort2(alist, l, u): print(alist) if l >= u: return m = l for i in xrange(l + 1, u + 1): if alist[i] < alist[l]: m += 1 alist[m], alist[i] = alist[i], alist[m] # swap between m and l after partition, important! alist[m], alist[l] = alist[l], alist[m] qsort2(alist, l, m - 1) qsort2(alist, m + 1, u) unsortedArray = [6, 5, 3, 1, 8, 7, 2, 4] print(qsort2(unsortedArray, 0, len(unsortedArray) - 1)) ~~~ ### Java ~~~ public class Sort { public static void main(String[] args) { int unsortedArray[] = new int[]{6, 5, 3, 1, 8, 7, 2, 4}; quickSort(unsortedArray); System.out.println("After sort: "); for (int item : unsortedArray) { System.out.print(item + " "); } } public static void quickSort1(int[] array, int l, int u) { for (int item : array) { System.out.print(item + " "); } System.out.println(); if (l >= u) return; int m = l; for (int i = l + 1; i <= u; i++) { if (array[i] < array[l]) { m += 1; int temp = array[m]; array[m] = array[i]; array[i] = temp; } } // swap between array[m] and array[l] // put pivot in the mid int temp = array[m]; array[m] = array[l]; array[l] = temp; quickSort1(array, l, m - 1); quickSort1(array, m + 1, u); } public static void quickSort(int[] array) { quickSort1(array, 0, array.length - 1); } } ~~~ 容易出錯的地方在于當前 partition 結束時未將 iii 和 mmm 交換。比較`alist[i]`和`alist[l]`時只能使用`<`而不是`<=`! 因為只有取`<`才能進入收斂條件，`<=`則可能會出現死循環，因為在`=`時第一個元素可能保持不變進而產生死循環。 相應的結果輸出為： ~~~ [6, 5, 3, 1, 8, 7, 2, 4] [4, 5, 3, 1, 2, 6, 8, 7] [2, 3, 1, 4, 5, 6, 8, 7] [1, 2, 3, 4, 5, 6, 8, 7] [1, 2, 3, 4, 5, 6, 8, 7] [1, 2, 3, 4, 5, 6, 8, 7] [1, 2, 3, 4, 5, 6, 8, 7] [1, 2, 3, 4, 5, 6, 7, 8] [1, 2, 3, 4, 5, 6, 7, 8] ~~~ ### Two-way partitioning 對于僅使用一個索引進行 partition 操作的快排對于隨機分布數列的效果還是不錯的，但若數組本身就已經有序或者相等的情況下，每次劃分僅能確定一個元素的最終位置，故最壞情況下的時間復雜度變為 O(n2)O(n^2)O(n2). 那么有什么辦法盡可能避免這種最壞情況嗎？聰明的人類總是能找到更好地解決辦法——使用兩個索引分別向右向左進行 partition. 先來一張動圖看看使用兩個索引進行 partition 的過程。  1. 選中`3`作為基準 1. `lo`指針指向元素`6`, `hi`指針指向`4`, 移動`lo`直至其指向的元素大于等于`3`, 移動`hi`直至其指向的元素小于`3`。找到后交換`lo`和`hi`指向的元素——交換元素`6`和`2`。 1. `lo`遞增，`hi`遞減，重復步驟2，此時`lo`指向元素為`5`, `hi`指向元素為`1`. 交換元素。 1. `lo`遞增，`hi`遞減，發現其指向元素相同，此輪劃分結束。遞歸排序元素`3`左右兩邊的元素。 對上述過程進行適當的抽象： 1. 下標 iii 和 jjj 初始化為待排序數組的兩端。 1. 基準元素設置為數組的第一個元素。 1. 執行 partition 操作，大循環內包含兩個內循環： - 左側內循環自增 iii, 直到遇到**不小于**基準元素的值為止。 - 右側內循環自減 jjj, 直到遇到**小于**基準元素的值為止。 1. 大循環測試兩個下標是否相等或交叉，交換其值。 這樣一來對于數組元素均相等的情形下，每次 partition 恰好在中間元素，故共遞歸調用 logn\log nlogn 次，每層遞歸調用進行 partition 操作的比較次數總和近似為 nnn. 故總計需 nlognn \log nnlogn 次比較。[programming_pearls](#) ### Python ~~~ #!/usr/bin/env python def qsort3(alist, l, u): print(alist) if l >= u: return t = alist[l] i = l + 1 j = u while True: while i <= u and alist[i] < t: i += 1 while alist[j] > t: j -= 1 if i > j: break # swap after make sure i > j alist[i], alist[j] = alist[j], alist[i] # do not forget swap l and j alist[l], alist[j] = alist[j], alist[l] qsort3(alist, l, j - 1) qsort3(alist, j + 1, u) unsortedArray = [6, 5, 3, 1, 8, 7, 2, 4] print(qsort3(unsortedArray, 0, len(unsortedArray) - 1)) ~~~ ### Java ~~~ public class Sort { public static void main(String[] args) { int unsortedArray[] = new int[]{6, 5, 3, 1, 8, 7, 2, 4}; quickSort(unsortedArray); System.out.println("After sort: "); for (int item : unsortedArray) { System.out.print(item + " "); } } public static void quickSort2(int[] array, int l, int u) { for (int item : array) { System.out.print(item + " "); } System.out.println(); if (l >= u) return; int pivot = array[l]; int left = l + 1; int right = u; while (left <= right) { while (left <= right && array[left] < pivot) { left++; } while (left <= right && array[right] >= pivot) { right--; } if (left > right) break; // swap array[left] with array[right] while left <= right int temp = array[left]; array[left] = array[right]; array[right] = temp; } /* swap the smaller with pivot */ int temp = array[right]; array[right] = array[l]; array[l] = temp; quickSort2(array, l, right - 1); quickSort2(array, right + 1, u); } public static void quickSort(int[] array) { quickSort2(array, 0, array.length - 1); } } ~~~ 相應的輸出為： ~~~ [6, 5, 3, 1, 8, 7, 2, 4] [2, 5, 3, 1, 4, 6, 7, 8] [1, 2, 3, 5, 4, 6, 7, 8] [1, 2, 3, 5, 4, 6, 7, 8] [1, 2, 3, 5, 4, 6, 7, 8] [1, 2, 3, 5, 4, 6, 7, 8] [1, 2, 3, 4, 5, 6, 7, 8] [1, 2, 3, 4, 5, 6, 7, 8] [1, 2, 3, 4, 5, 6, 7, 8] [1, 2, 3, 4, 5, 6, 7, 8] [1, 2, 3, 4, 5, 6, 7, 8] ~~~ 從以上3種快排的實現我們可以發現其與『歸并排序』的區別主要有如下兩點： 1. 歸并排序將數組分成兩個子數組分別排序，并將有序的子數組歸并以將整個數組排序。遞歸調用發生在處理整個數組之前。 1. 快速排序將一個數組分成兩個子數組并對這兩個子數組獨立地排序，兩個子數組有序時整個數組也就有序了。遞歸調用發生在處理整個數組之后。 Robert Sedgewick 在其網站上對 [Quicksort](http://algs4.cs.princeton.edu/23quicksort/) 做了較為完整的介紹，建議去圍觀下。 ### Reference - [快速排序 - 維基百科，自由的百科全書](http://zh.wikipedia.org/wiki/%E5%BF%AB%E9%80%9F%E6%8E%92%E5%BA%8F) - [Quicksort | Robert Sedgewick](http://algs4.cs.princeton.edu/23quicksort/) - Programming Pearls Column 11 Sorting - 深入探討了插入排序和快速排序 - [Quicksort Analysis](#) - programming_pearls > . Programming Pearls(第二版修訂版) 一書中第11章排序中注明需要 nlog2nn\log2nnlog2n > 次比較，翻譯有誤？ [ ?](# "Jump back to footnote [programming_pearls] in the text.")