前言
之前我們介紹了交換類排序中的冒泡排序，這次我們介紹另一種交換類排序叫做快速排序。快速排序的優點是原地排序，不佔用額外空間，時間複雜度是O(nlogn)。
當然，對於快速排序來說，它也是有缺點的，它對於含有大量重複元素的數組排序效率是非常低的，時間複雜度會降為O(n^2)。此時需要使用改進的快速排序—雙路快速排序，在雙路快速排序的基礎上，我們又進一步優化得到了三路快速排序。
快速排序
快速排序的基本思想是：通過一趟排序將要排序的數據分割成獨立的兩部分，其中一部分的所有數據都比另外一部分的所有數據都要小，然後再按此方法對這兩部分數據分別進行快速排序，整個排序過程可以遞歸進行，以此達到整個數據變成有序序列。
快速排序的步驟如下：
把第一個元素作為分界的標定點，用l指向它。遍歷右邊元素，在遍歷的過程中，我們整理數組，一部分小於v，一部分大於v，用j指向小於v和大於v的分界點，用i指向當前訪問的元素e，此時，數組arr[l+1...j]v。若e>v，那麼直接將e合併在大於v那麼部分的後面，然後i++繼續比較後面的元素。若e使用這種方式對整個數組進行一次遍歷，遍歷完後數組被分成三部分，左邊部分是v，中間部分是>v，右邊部分是最後，我們讓l指向的元素和j指向的元素交換，這樣就v這個元素進行了快速排序，v左邊元素都小於v，右邊元素都大於v。現在我們使用上述方法對數組[2, 1, 4, 3, 7, 8, 5, 6]進行快速排序，下圖展示了整個快速排序的過程：
快速排序代碼：
<code>public static void sort(Comparable[] arr) { int n = arr.length; sort(arr, 0, n - 1);}// 遞歸使用快速排序,對arr[l...r]的範圍進行排序private static void sort(Comparable[] arr, int l, int r) { if (l >= r) { return; } // 對arr[l...r]部分進行partition操作, 返回p, 使得arr[l...p-1] < arr[p] ; arr[p+1...r] > arr[p] int p = partition(arr, l, r); sort(arr, l, p - 1); sort(arr, p + 1, r);}private static int partition(Comparable[] arr, int l, int r) { // 最左元素作為標定點 Comparable v = arr[l]; int j = l; for (int i = l + 1; i <= r; i++) { if (arr[i].compareTo(v) < 0) { swap(arr, j + 1, i); j++; } } swap(arr, l, j); return j;}/<code>
優化的快速排序
經過上述介紹，我們可以發現快速排序不能保證每次切分的子數組大小相等，因此就可能一邊很小，一邊很大。對於一個有序數組，快速排序的時間複雜度就變成了O(n^2)，相當於樹退化成了鏈表，下圖展示了這種變化：
上述我們是固定使用左邊的第一個元素作為標定元素，現在我們隨機挑選一個元素作為標定元素。此時我們第一次選中第一個元素的概率為 1/n，第二次又選中第二個元素 1/n-1，以此類推，發生之前退化成鏈表的概率為1/n(n-1)(n-2)....，當 n 很大時，這種概率幾乎為 0。
另一個優化就是對小規模數組使用插入排序，因為遞歸會使得小規模問題中方法的調用過於頻繁，而插入排序對小規模數組排序是非常快的。
優化的快速排序代碼：
<code>public static void sort(Comparable[] arr) { int n = arr.length; sort(arr, 0, n - 1);}// 遞歸使用快速排序,對arr[l...r]的範圍進行排序private static void sort(Comparable[] arr, int l, int r) { // 對於小規模數組, 使用插入排序 if (r - l <= 15) { InsertionSort.sort(arr, l, r); return; } // 對arr[l...r]部分進行partition操作, 返回p, 使得arr[l...p-1] < arr[p] ; arr[p+1...r] > arr[p] int p = partition(arr, l, r); sort(arr, l, p - 1); sort(arr, p + 1, r);}private static int partition(Comparable[] arr, int l, int r) { // 隨機在arr[l...r]的範圍中, 選擇一個數值作為標定點pivot swap(arr, l, (int) (Math.random() * (r - l + 1)) + l); Comparable v = arr[l]; int j = l; for (int i = l + 1; i <= r; i++) { if (arr[i].compareTo(v) < 0) { swap(arr, j + 1, i); j++; } } swap(arr, l, j); return j;}/<code>
雙路快速排序
對於含有大量重複元素的數組，使用上述的快速排序效率是非常低的，因為在我們上面的判斷中，如果元素小於v，則將元素放在v部分。此時，如果數組中有大量重複元素，>v部分會變得很長，導致左右兩邊不均衡，性能降低。
雙路快速排序的步驟如下：
將v兩部分放在數組的兩端，用i指向v部分的前一個元素。從i開始向後遍歷，如果遍歷的元素e=v，則停止遍歷。同樣從j開始向前遍歷，如果遍歷的元素e>v，則繼續向前遍歷，直到遍歷的元素e<=v，則停止遍歷。交換i指向的元素和j指向的元素。然後i++，j--繼續比較下一個。雙路快速排序的代碼：
<code>public static void sort(Comparable[] arr) { int n = arr.length; sort(arr, 0, n - 1);}private static void sort(Comparable[] arr, int l, int r) { // 對於小規模數組, 使用插入排序 if (r - l <= 15) { InsertionSort.sort(arr, l, r); return; } int p = partition(arr, l, r); sort(arr, l, p - 1); sort(arr, p + 1, r);}private static int partition(Comparable[] arr, int l, int r) { // 隨機在arr[l...r]的範圍中, 選擇一個數值作為標定點pivot swap(arr, l, (int) (Math.random() * (r - l + 1)) + l); Comparable v = arr[l]; int i = l + 1, j = r; while (true) { // 注意這裡的邊界, arr[i].compareTo(v) < 0, 不能是arr[i].compareTo(v) <= 0 // 不加等號如果遇到相等的情況，這時候while循環就會退出，即交換i和j的值，使得對於包含大量相同元素的數組， 雙方相等的數據就會交換，這樣就可以一定程度保證兩路的數據量平衡 // 從i開始向後遍歷，如果遍歷的元素e=v，則停止遍歷 while (i <= r && arr[i].compareTo(v) < 0) { i++; } // 從j開始向前遍歷，如果遍歷的元素e>v，則繼續向前遍歷，直到遍歷的元素e<=v，則停止遍歷 while (j >= l + 1 && arr[j].compareTo(v) > 0) { j--; } if (i >= j) { break; } swap(arr, i, j); i++; j--; } // 此時j指向的元素是數組中最後一個小於v的元素, i指向的元素是數組中第一個大於v的元素 swap(arr, l, j); return j;}/<code>
三路快速排序
三路快速排序的步驟如下：
在雙路快速排序的基礎上，我們把等於v的元素單獨作為一個部分。lt指向小於v部分的最後一個元素，gt指向大於v部分的第一個元素。從i開始向後遍歷，如果遍歷的元素e=v，則e直接合併到=v部分，然後i++繼續遍歷。如果遍歷的元素ev，則將e和>v部分前一個元素（gt-1指向的元素）交換，然後gt--，不過此時i不需要改變，因為i位置的元素是和gt位置前面的空白元素交換過來的。遍歷完後i=gt，然後將l指向元素和lt指向元素交換。對v部分進行以上操作。三路快速排序相比雙路快速排序的優勢在於：減少了對重複元素的比較操作，因為重複元素在一次排序中就已經作為單獨一部分排好了，之後只需要對不等於該重複元素的其他元素進行排序。
三路快速排序代碼：
<code>public static void sort(Comparable[] arr) { int n = arr.length; sort(arr, 0, n - 1);}private static void sort(Comparable[] arr, int l, int r) { // 對於小規模數組, 使用插入排序 if (r - l <= 15) { InsertionSort.sort(arr, l, r); return; } // 隨機在arr[l...r]的範圍中, 選擇一個數值作為標定點pivot swap(arr, l, (int) (Math.random() * (r - l + 1)) + l); Comparable v = arr[l]; int lt = l; // arr[l+1...lt] < v int gt = r + 1; // arr[gt...r] > v int i = l + 1; // arr[lt+1...i) == v while (i < gt) { if (arr[i].compareTo(v) < 0) { swap(arr, i, lt + 1); i++; lt++; } else if (arr[i].compareTo(v) > 0) { swap(arr, i, gt - 1); gt--; } else { // arr[i] == v i++; } } swap(arr, l, lt); sort(arr, l, lt - 1); sort(arr, gt, r);}/<code>
總結
本文介紹了快速排序、快速排序的優化、雙路快速排序和三路快速排序。
對於快速排序，我們需要選擇合適的標定點，使得標定點的兩邊平衡；在快速排序中遞歸到小數組時，我們可以使用插入排序替換遞歸，減少不必要的開銷。
對於雙路快速排序和三路快速排序，我們使用的場合是數組中存在大量重複元素。
最後，提示一下 JDK 底層的排序使用的就是插入排序 + 雙路快速排序 + 歸併排序的組合。