圖解快速排序及雙路三路快速排序

前言

之前我們介紹了交換類排序中的冒泡排序，這次我們介紹另一種交換類排序叫做快速排序。快速排序的優點是原地排序，不佔用額外空間，時間複雜度是O(nlogn)。

當然，對於快速排序來說，它也是有缺點的，它對於含有大量重複元素的數組排序效率是非常低的，時間複雜度會降為O(n^2)。此時需要使用改進的快速排序—雙路快速排序，在雙路快速排序的基礎上，我們又進一步優化得到了三路快速排序。

快速排序

快速排序的基本思想是：通過一趟排序將要排序的數據分割成獨立的兩部分，其中一部分的所有數據都比另外一部分的所有數據都要小，然後再按此方法對這兩部分數據分別進行快速排序，整個排序過程可以遞歸進行，以此達到整個數據變成有序序列。

快速排序的步驟如下：

0. 把第一個元素作為分界的標定點，用l指向它。
1. 遍歷右邊元素，在遍歷的過程中，我們整理數組，一部分小於v，一部分大於v，用j指向小於v和大於v的分界點，用i指向當前訪問的元素e，此時，數組arr[l+1...j]v。
2. 若e>v，那麼直接將e合併在大於v那麼部分的後面，然後i++繼續比較後面的元素。
3. 若e
4. 使用這種方式對整個數組進行一次遍歷，遍歷完後數組被分成三部分，左邊部分是v，中間部分是>v，右邊部分是
5. 最後，我們讓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部分會變得很長，導致左右兩邊不均衡，性能降低。

雙路快速排序的步驟如下：

0. 將v兩部分放在數組的兩端，用i指向v部分的前一個元素。
1. 從i開始向後遍歷，如果遍歷的元素e=v，則停止遍歷。同樣從j開始向前遍歷，如果遍歷的元素e>v，則繼續向前遍歷，直到遍歷的元素e<=v，則停止遍歷。
2. 交換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>

三路快速排序

三路快速排序的步驟如下：

0. 在雙路快速排序的基礎上，我們把等於v的元素單獨作為一個部分。lt指向小於v部分的最後一個元素，gt指向大於v部分的第一個元素。
1. 從i開始向後遍歷，如果遍歷的元素e=v，則e直接合併到=v部分，然後i++繼續遍歷。如果遍歷的元素ev，則將e和>v部分前一個元素（gt-1指向的元素）交換，然後gt--，不過此時i不需要改變，因為i位置的元素是和gt位置前面的空白元素交換過來的。
2. 遍歷完後i=gt，然後將l指向元素和lt指向元素交換。
3. 對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 底層的排序使用的就是插入排序 + 雙路快速排序 + 歸併排序的組合。

閱讀更多 放開我我還能學 的文章

關鍵字: 元素 ... 雙路