十大經典排序算法（二）

接上一篇

6 快速排序（Quick Sort）

快速排序（有時稱為分區交換排序）是一種有效的排序算法。由英國計算機科學家Tony Hoare於1959年開發並於1961年發表，它仍然是一種常用的排序算法。如果實施得當，它可以比主要競爭對手（合併排序和堆排序）快兩到三倍。快速排序基本上被認為是相同數量級的所有排序算法中，平均性能最好的。

Quicksort是一種分而治之的算法。它通過從數組中選擇一個“pivot”元素並將其他元素劃分為兩個子數組（根據它們是否小於或大於樞軸）來工作。然後將子數組遞歸排序。這種排序方式由於可以就地完成，所以需要少量額外的內存來執行排序。

在平均狀況下，排序 n 個項目要 Ο(nlogn) 次比較。在最壞狀況下則需要 Ο(n2) 次比較，但這種狀況並不常見。事實上，快速排序通常明顯比其他 Ο(nlogn) 算法更快，因為它的內部循環（inner loop）可以在大部分的架構上很有效率地被實現出來

其廣泛應用的主要原因是高效.

舉個例子 如無序數組[6 2 4 1 5 9]

• 先把第一項[6]取出來,

用[6]依次與其餘項進行比較,

如果比[6]小就放[6]前邊,2 4 1 5都比[6]小,所以全部放到[6]前邊

如果比[6]大就放[6]後邊,9比[6]大,放到[6]後邊

//6出列後大喝一聲,比我小的站前邊,比我大的站後邊,行動吧!霸氣十足~

一趟排完後變成下邊這樣:

排序前 6 2 4 1 5 9 排序後 2 4 1 5 6 9

• 對前半拉[2 4 1 5]繼續進行快速排序

重複第一步後變成下邊這樣:

排序前 2 4 1 5 排序後 1 2 4 5

前半拉排序完成,總的排序也完成

排序前:[6 2 4 1 5 9] 排序後:[1 2 4 5 6 9]

• 排序結束

算法描述

快速排序使用分治法來把一個串（list）分為兩個子串（sub-lists）。具體算法描述如下：

• 從數列中挑出一個元素，稱為 “基準”（pivot）；
• 重新排序數列，所有元素比基準值小的擺放在基準前面，所有元素比基準值大的擺在基準的後面（相同的數可以到任一邊）。在這個分區退出之後，該基準就處於數列的中間位置。這個稱為分區（partition）操作；
• 遞歸地（recursive）把小於基準值元素的子數列和大於基準值元素的子數列排序。

動圖演示

代碼實現

<code>import java.util.Arrays;

public class QuickSort {

  public int[] sort(int[] sourceArray) {
    // 對 arr 進行拷貝，不改變參數內容
    int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);

    return quickSort(arr, 0, arr.length - 1);
  }

  private int[] quickSort(int[] arr, int left, int right) {

    if (left < right) {
      int partitionIndex = partition(arr, left, right);
      quickSort(arr, left, partitionIndex - 1);
      quickSort(arr, partitionIndex + 1, right);
    }
    return arr;

  }

  private int partition(int[] arr, int left, int right) {

    int pivot = arr[right];
    int index = left;
    for (int i = index; i <= right; i++) {

      if (arr[i] <= pivot) {
        int temp = arr[i];
        arr[i] = arr[index];
        arr[index] = temp;
        index++;
      }

    }
    return index - 1; 


  }


}/<code>

為了便於理解 ，再舉個例子，先把數組按最後一個元素4作為分界點，把數組一分為三。除了分界點之外，左子部分全是小於等於4的，右子部分全是大於4的，它們可以進一步遞歸排序。該算法的核心是：如何把數組按分界點一分為三？

具體過程是這樣的，選取最後一個元素為分界點，然後遍歷數組找小於等於分界點的元素，然後往數組前面交換。比如：

上圖中，我們按順序找小於等於4的元素，共1、2、3、4。然後分別與數組的前4個元素交換即可，結果自然是一分為三。

基準的選擇

• 基準普遍的有三種選擇方法：
  固定基準元，一般選取中間值或頭部值或尾部值。如果輸入序列是隨機的，處理時間是可以接受的。如果數組已經有序時或部分有序，此時的分割就是一個非常不好的分割。因為每次劃分只能使待排序序列減一，數組全部有序時，此時為最壞情況，快速排序淪為冒泡排序，時間複雜度為O(n^2)。所以此種方式要慎用。
• 隨機基準元，這是一種相對安全的策略。由於基準元的位置是隨機的，那麼產生的分割也不會總是會出現劣質的分割。在整個數組數字全相等時，仍然是最壞情況，時間複雜度是O(n^2）。實際上，隨機化快速排序得到理論最壞情況的可能性僅為1/(2^n）。所以隨機化快速排序可以對於絕大多數輸入數據達到O(nlogn）的期望時間複雜度。
• 三數取中，一般是分別取出數組的頭部元素，尾部元素和中部元素， 在這三個數中取出中位數，作為基準元素。最佳的劃分是將待排序的序列分成等長的子序列，最佳的狀態我們可以使用序列的中間的值，也就是第N/2個數。可是，這很難算出來，並且會明顯減慢快速排序的速度。這樣的中值的估計可以通過隨機選取三個元素並用它們的中值作為樞紐元而得到。事實上，隨機性並沒有多大的幫助，因此一般的做法是使用左端、右端和中心位置上的三個元素的中值作為樞紐元。顯然使用三數中值分割法消除了預排序輸入的不好情形。（簡單來說，就是隨機取三個數，取中位數）。

優化思路

• 當待排序序列的長度分割到一定大小後，使用插入排序。

jdk8的源碼也是這麼寫的 （注意註釋部分，這裡INSERTION_SORT_THRESHOLD = 47）

原因：對於很小和部分有序的數組，快排不如插排好。當待排序序列的長度分割到一定大小後，繼續分割的效率比插入排序要差，此時可以使用插排而不是快排。

• 合理選擇pivot pivot選取的理想情況是：讓分區中比 pivot 小的元素數量和比 pivot 大的元素數量差不多。較常用的做法是三數取中（ midian of three ），即從第一項、最後一項、中間一項中取中位數作為 pivot。當然這並不能完全避免最差情況的發生。所以很多時候會採取更小心、更嚴謹的 pivot 選擇方案（對於大數組特別重要）。比如先把大數組平均切分成左中右三個部分，每個部分用三數取中得到一箇中位數，再從得到的三個中位數中找出中位數。
• 優化遞歸操作快排函數在函數尾部有兩次遞歸操作，我們可以對其使用尾遞歸優化（然而並不是所有語言都支持尾遞歸）

　　 優點：如果待排序的序列劃分極端不平衡，遞歸的深度將趨近於n，而棧的大小是很有限的，每次遞歸調用都會耗費一定的棧空間，函數的參數越多，每次遞歸耗費的空間也越多。

優化後，可以縮減堆棧深度，由原來的O(n)縮減為O(logn)，將會提高性能。

• 改進劃分的策略（可以參考 https://segmentfault.com/a/1190000014960548）jdk8 DualPivotQuicksort 使用了一種稱為 五取樣劃分 的策略對數組進行劃分，類似於 BFPRT 算法。
• 雙樞軸（可以參考 https://segmentfault.com/a/1190000014960548） 即將數組三切分(大於樞軸，等於樞軸，小於樞軸），可以證明這樣是熵最優的並且更高效。為什麼這樣劃分呢？因為統計表明對大規模數組進行排序時，數據重複的情況比較多，因此使用雙樞軸可以有效避免相等元素之間的比較。以 Java 標準庫為例，JDK 1.8 中的 DualPivotQuicksort 實現了一種 快速三向切分 的快速排序，它通過將相等元素聚集起來的方式使熵最優（原理：將相等元素聚集起來，不必再切分這些元素）。
• 其他未寫到，或更加喪心病狂的方法

參考：

• https://www.programcreek.com/2012/11/quicksort-array-in-java/
• https://juejin.im/post/5d75f77e5188253e4b2f0d3d
• https://www.kancloud.cn/maliming/leetcode/740422

閱讀更多 小盒子的技術分享 的文章

關鍵字: 經典 算法 排序