快速排序

本頁面將簡要介紹快速排序。

定義

快速排序（英語：Quicksort），又稱分區交換排序（英語：partition-exchange sort），簡稱「快排」，是一種被廣泛運用的排序算法。

基本原理與實現

過程

快速排序的工作原理是通過分治的方式來將一個數組排序。

快速排序分為三個過程：

將數列劃分為兩部分（要求保證相對大小關係）；
遞歸到兩個子序列中分別進行快速排序；
不用合併，因為此時數列已經完全有序。

和歸併排序不同，第一步並不是直接分成前後兩個序列，而是在分的過程中要保證相對大小關係。具體來説，第一步要是要把數列分成兩個部分，然後保證前一個子數列中的數都小於後一個子數列中的數。為了保證平均時間複雜度，一般是隨機選擇一個數 \(m\) 來當做兩個子數列的分界。

之後，維護一前一後兩個指針 \(p\) 和 \(q\)，依次考慮當前的數是否放在了應該放的位置（前還是後）。如果當前的數沒放對，比如説如果後面的指針 \(q\) 遇到了一個比 \(m\) 小的數，那麼可以交換 \(p\) 和 \(q\) 位置上的數，再把 \(p\) 向後移一位。當前的數的位置全放對後，再移動指針繼續處理，直到兩個指針相遇。

其實，快速排序沒有指定應如何具體實現第一步，不論是選擇 \(m\) 的過程還是劃分的過程，都有不止一種實現方法。

第三步中的序列已經分別有序且第一個序列中的數都小於第二個數，所以直接拼接起來就好了。

C++²Python²

struct Range {
  int start, end;

  Range(int s = 0, int e = 0) { start = s, end = e; }
};

template <typename T>
void quick_sort(T arr[], const int len) {
  if (len <= 0) return;
  Range r[len];
  int p = 0;
  r[p++] = Range(0, len - 1);
  while (p) {
    Range range = r[--p];
    if (range.start >= range.end) continue;
    T mid = arr[range.end];
    int left = range.start, right = range.end - 1;
    while (left < right) {
      while (arr[left] < mid && left < right) left++;
      while (arr[right] >= mid && left < right) right--;
      std::swap(arr[left], arr[right]);
    }
    if (arr[left] >= arr[range.end])
      std::swap(arr[left], arr[range.end]);
    else
      left++;
    r[p++] = Range(range.start, left - 1);
    r[p++] = Range(left + 1, range.end);
  }
}

def quick_sort(alist, first, last):
    if first >= last:
        return
    mid_value = alist[first]
    low = first
    high = last
    while low < high:
        while low < high and alist[high] >= mid_value:
            high -= 1
        alist[low] = alist[high]
        while low < high and alist[low] < mid_value:
            low += 1
        alist[high] = alist[low]
    alist[low] = mid_value
    quick_sort(alist, first, low - 1)
    quick_sort(alist, low + 1, last)

性質

穩定性

快速排序是一種不穩定的排序算法。

時間複雜度

快速排序的最優時間複雜度和平均時間複雜度為 \(O(n\log n)\)，最壞時間複雜度為 \(O(n^2)\)。

對於最優情況，每一次選擇的分界值都是序列的中位數，此時算法時間複雜度滿足的遞推式為 \(T(n) = 2T(\dfrac{n}{2}) + \Theta(n)\)，由主定理，\(T(n) = \Theta(n\log n)\)。

對於最壞情況，每一次選擇的分界值都是序列的最值，此時算法時間複雜度滿足的遞推式為 \(T(n) = T(n - 1) + \Theta(n)\)，累加可得 \(T(n) = \Theta(n^2)\)。

對於平均情況，每一次選擇的分界值可以看作是等概率隨機的。

證明

下面我們來證明這種情況下算法的時間複雜度是 \(O(n\log n)\)。

引理 1： 當對 \(n\) 個元素的數組進行快速排序時，假設在劃分元素時總共的比較次數為 \(X\)，則快速排序的時間複雜度是 \(O(n + X)\)。

由於在每次劃分元素的過程中，都會選擇一個元素作為分界，所以劃分元素的過程至多發生 \(n\) 次。又由於劃分元素的過程中比較的次數和其他基礎操作的次數在一個數量級，所以總時間複雜度是 \(O(n + X)\) 的。

設 \(a_i\) 為原數組中第 \(i\) 小的數，定義 \(A_{i,j}\) 為 \(\{ a_i, a_{i+1}, \dots, a_j \}\)，\(X_{i,j}\) 是一個取值為 \(0\) 或者 \(1\) 的離散隨機變量表示在排序過程中 \(a_i\) 是否和 \(a_j\) 發生比較。

顯然每次選取的分界值是不同的，而元素只會和分界值比較，所以總比較次數

\[ \begin{aligned} X = \sum \limits _ {i = 1} ^ {n - 1} \sum \limits _ {j = i + 1} ^ n X_{i,j} \end{aligned} \]

由期望的線性性，

\[ \begin{aligned} E[X] & = E \left[ \sum \limits _ {i = 1} ^ {n - 1} \sum \limits _ {j = i + 1} ^ n X_{i,j} \right] \\ & = \sum \limits _ {i = 1} ^ {n - 1} \sum \limits _ {j = i + 1} ^ n E[X_{i,j}] \\ & = \sum \limits _ {i = 1} ^ {n - 1} \sum \limits _ {j = i + 1} ^ n P(a_i\ \text{和}\ a_j\ \text{比較}) \end{aligned} \]

引理 2： \(a_i\) 和 \(a_j\) 比較的充要條件是 \(a_i\) 或 \(a_j\) 是集合 \(A_{i,j}\) 中第一個被選中的分界值。

先證必要性，即若 \(a_i\) 和 \(a_j\) 都不是集合 \(A_{i,j}\) 中第一個被選中的分界值，則 \(a_i\) 不和 \(a_j\) 比較。

若 \(a_i\) 和 \(a_j\) 都不是集合 \(A_{i,j}\) 中第一個被選中的分界值，則一定存在一個 \(x\) 滿足 \(i < x < j\)，使得 \(a_x\) 是 \(A_{i,j}\) 中第一個被選中的分界值。在以 \(a_x\) 為分界值的劃分中，\(a_i\) 和 \(a_j\) 被劃分到數組的兩個不同的子序列中，所以之後 \(a_i\) 和 \(a_j\) 一定不會比較。又因為元素只和分界值比較，所以 \(a_i\) 和 \(a_j\) 在此次劃分前和劃分中沒有比較。所以 \(a_i\) 不和 \(a_j\) 比較。

再證充分性，即若 \(a_i\) 或 \(a_j\) 是集合 \(A_{i,j}\) 中第一個被選中的分界值，則 \(a_i\) 和 \(a_j\) 比較。

不失一般地，假設 \(a_i\) 是集合 \(A_{i,j}\) 中第一個被選中的分界值。由於 \(A_{i,j}\) 中沒有其他數選為分界值，所以 \(A_{i,j}\) 中的元素都在數組的同一子序列中。在以 \(a_i\) 為分界值的劃分中，\(a_i\) 和當前子序列中所有元素都進行了比較，所以 \(a_i\) 和 \(a_j\) 進行了比較。

考慮計算 \(P(a_i\ \text{和}\ a_j\ \text{比較})\)。在 \(A_{i,j}\) 中某個元素被選為分界值之前，\(A_{i,j}\) 中的元素都在數組的同一子序列中。所以 \(A_{i,j}\) 中每個元素都會被等可能地第一個被選為分界值。由於 \(A_{i,j}\) 中有 \(j - i + 1\) 個元素，由引理 2，

\[ P(a_i \text{和} a_j \text{比較}) = P(a_i \text{或} a_j \text{是集合} A_{i,j} \text{中第一個被選中的分界值}) = \dfrac{2}{j-i+1} \]

所以

\[ \begin{aligned} E[X] & = \sum \limits _ {i = 1} ^ {n - 1} \sum \limits _ {j = i + 1} ^ n P(a_i\ \text{和}\ a_j\ \text{比較}) \\ & = \sum \limits _ {i = 1} ^ {n - 1} \sum \limits _ {j = i + 1} ^ n \dfrac{2}{j - i + 1} \\ & = \sum \limits _ {i = 1} ^ {n - 1} \sum \limits _ {k = 2} ^ {n - i + 1} \dfrac{2}{k} \\ & = \sum \limits _ {i = 1} ^ {n - 1} O(\log n) \\ & = O(n \log n) \end{aligned} \]

由此，快速排序的期望時間複雜度為 \(O(n \log n)\)。

在實踐中，幾乎不可能達到最壞情況，而快速排序的內存訪問遵循局部性原理，所以多數情況下快速排序的表現大幅優於堆排序等其他複雜度為 \(O(n \log n)\) 的排序算法。¹

優化

樸素優化思想

如果僅按照上文所述的基本思想來實現快速排序（或者是直接照抄模板）的話，那大概率是通不過 P1177【模板】快速排序這道模板的。因為有毒瘤數據能夠把樸素的快速排序卡成 \(O(n^2)\)。

所以，我們需要對樸素快速排序思想加以優化。較為常見的優化思路有以下三種³。

通過 三數取中（即選取第一個、最後一個以及中間的元素中的中位數） 的方法來選擇兩個子序列的分界元素（即比較基準）。這樣可以避免極端數據（如升序序列或降序序列）帶來的退化；
當序列較短時，使用 插入排序 的效率更高；
每趟排序後，將與分界元素相等的元素聚集在分界元素周圍，這樣可以避免極端數據（如序列中大部分元素都相等）帶來的退化。

下面列舉了幾種較為成熟的快速排序優化方式。

三路快速排序

定義

三路快速排序（英語：3-way Radix Quicksort）是快速排序和基數排序的混合。它的算法思想基於荷蘭國旗問題的解法。

過程

與原始的快速排序不同，三路快速排序在隨機選取分界點 \(m\) 後，將待排數列劃分為三個部分：小於 \(m\)、等於 \(m\) 以及大於 \(m\)。這樣做即實現了將與分界元素相等的元素聚集在分界元素周圍這一效果。

性質

三路快速排序在處理含有多個重複值的數組時，效率遠高於原始快速排序。其最佳時間複雜度為 \(O(n)\)。

實現

三路快速排序實現起來非常簡單，下面給出了一種三路快排的 C++ 實現。

C++Python²

// 模板的 T 參數表示元素的類型，此類型需要定義小於（<）運算
template <typename T>
// arr 為需要被排序的數組，len 為數組長度
void quick_sort(T arr[], const int len) {
  if (len <= 1) return;
  // 隨機選擇基準（pivot）
  const T pivot = arr[rand() % len];
  // i：當前操作的元素下標
  // arr[0, j)：存儲小於 pivot 的元素
  // arr[k, len)：存儲大於 pivot 的元素
  int i = 0, j = 0, k = len;
  // 完成一趟三路快排，將序列分為：
  // 小於 pivot 的元素 | 等於 pivot 的元素 | 大於 pivot 的元素
  while (i < k) {
    if (arr[i] < pivot)
      swap(arr[i++], arr[j++]);
    else if (pivot < arr[i])
      swap(arr[i], arr[--k]);
    else
      i++;
  }
  // 遞歸完成對於兩個子序列的快速排序
  quick_sort(arr, j);
  quick_sort(arr + k, len - k);
}

def quick_sort(arr, l, r):
    if l >= r:
        return
    random_index = random.randint(l, r)
    pivot = arr[random_index]
    arr[l], arr[random_index] = arr[random_index], arr[l]
    i = l + 1
    j = l 
    k = r + 1
    while i < k:
        if arr[i] < pivot:
            arr[i], arr[j + 1] = arr[j + 1], arr[i]
            j += 1
            i += 1
        elif arr[i] > pivot:
            arr[i], arr[k - 1] = arr[k - 1], arr[i]
            k -= 1
        else: 
            i += 1
    arr[l], arr[j] = arr[j], arr[l]
    quick_sort(arr, l, j - 1)
    quick_sort(arr, k, r)

內省排序

定義

內省排序（英語：Introsort 或 Introspective sort）⁴是快速排序和堆排序的結合，由 David Musser 於 1997 年發明。內省排序其實是對快速排序的一種優化，保證了最差時間複雜度為 \(O(n\log n)\)。

性質

內省排序將快速排序的最大遞歸深度限制為 \(\lfloor \log_2n \rfloor\)，超過限制時就轉換為堆排序。這樣既保留了快速排序內存訪問的局部性，又可以防止快速排序在某些情況下性能退化為 \(O(n^2)\)。

實現

從 2000 年 6 月起，SGI C++ STL 的 stl_algo.h 中 sort() 函數的實現採用了內省排序算法。

線性找第 k 大的數

在下面的代碼示例中，第 \(k\) 大的數被定義為序列排成升序時，第 \(k\) 個位置上的數（編號從 0 開始）。

找第 \(k\) 大的數（K-th order statistic），最簡單的方法是先排序，然後直接找到第 \(k\) 大的位置的元素。這樣做的時間複雜度是 \(O(n\log n)\)，對於這個問題來説很不划算。

我們可以藉助快速排序的思想解決這個問題。考慮快速排序的劃分過程，在快速排序的「劃分」結束後，數列 \(A_{p} \cdots A_{r}\) 被分成了 \(A_{p} \cdots A_{q}\) 和 \(A_{q+1} \cdots A_{r}\)，此時可以按照左邊元素的個數（\(q - p + 1\)）和 \(k\) 的大小關係來判斷是隻在左邊還是隻在右邊遞歸地求解。

和快速排序一樣，該方法的時間複雜度依賴於每次劃分時選擇的分界值。如果採用隨機選取分界值的方式，可以證明在期望意義下，程序的時間複雜度為 \(O(n)\)。

實現（C++）

// 模板的 T 參數表示元素的類型，此類型需要定義小於（<）運算
template <typename T>
// arr 為查找範圍數組，rk 為需要查找的排名（從 0 開始），len 為數組長度
T find_kth_element(T arr[], int rk, const int len) {
  if (len <= 1) return arr[0];
  // 隨機選擇基準（pivot）
  const T pivot = arr[rand() % len];
  // i：當前操作的元素
  // j：第一個等於 pivot 的元素
  // k：第一個大於 pivot 的元素
  int i = 0, j = 0, k = len;
  // 完成一趟三路快排，將序列分為：
  // 小於 pivot 的元素 ｜ 等於 pivot 的元素 ｜ 大於 pivot 的元素
  while (i < k) {
    if (arr[i] < pivot)
      swap(arr[i++], arr[j++]);
    else if (pivot < arr[i])
      swap(arr[i], arr[--k]);
    else
      i++;
  }
  // 根據要找的排名與兩條分界線的位置，去不同的區間遞歸查找第 k 大的數
  // 如果小於 pivot 的元素個數比k多，則第 k 大的元素一定是一個小於 pivot 的元素
  if (rk < j) return find_kth_element(arr, rk, j);
  // 否則，如果小於 pivot 和等於 pivot 的元素加起來也沒有 k 多，
  // 則第 k 大的元素一定是一個大於 pivot 的元素
  else if (rk >= k)
    return find_kth_element(arr + k, rk - k, len - k);
  // 否則，pivot 就是第 k 大的元素
  return pivot;
}

改進：中位數中的中位數

中位數中的中位數（英文：Median of medians），提供了一種確定性的選擇劃分過程中分界值的方法，從而能夠讓找第 \(k\) 大的數算法在最壞情況下也能實現線性時間複雜度。

該算法的流程如下：

將整個序列劃分為 \(\left \lfloor \dfrac{n}{5} \right \rfloor\) 組，每組元素數不超過 5 個；
尋找每組元素的中位數（因為元素個數較少，可以直接使用插入排序等算法）。
找出這 \(\left \lfloor \dfrac{n}{5} \right \rfloor\) 組元素中位數中的中位數。將該元素作為前述算法中每次劃分時的分界值即可。

時間複雜度證明

下面將證明，該算法在最壞情況下的時間複雜度為 \(O(n)\)。設 \(T(n)\) 為問題規模為 \(n\) 時，解決問題需要的計算量。

先分析前兩步——劃分與尋找中位數。由於劃分後每組內的元素數量非常少，可以認為尋找一組元素的中位數的時間複雜度為 \(O(1)\)。因此找出所有 \(\left \lfloor \dfrac{n}{5} \right \rfloor\) 組元素中位數的時間複雜度為 \(O(n)\)。

接下來分析第三步——遞歸過程。這一步進行了兩次遞歸調用：第一次是尋找各組中位數中的中位數，需要的開銷顯然為 \(T(\dfrac{n}{5})\)，第二次是進入分界值的左側部分或右側部分。根據我們選取的劃分元素，有 \(\dfrac{1}{2} \times \left \lfloor \dfrac{n}{5} \right \rfloor = \left \lfloor \dfrac{n}{10} \right \rfloor\) 組元素的中位數小於分界值，這幾組元素中，比中位數還小的元素也一定比分界值要小，從而整個序列中小於分界值的元素至少有 \(3 \times \left \lfloor \dfrac{n}{10} \right \rfloor = \left \lfloor \dfrac{3n}{10} \right \rfloor\) 個。同理，整個序列中大於分界值的元素也至少有 \(\left \lfloor \dfrac{3n}{10} \right \rfloor\) 個。因此，分界值的左邊或右邊至多有 \(\dfrac{7n}{10}\) 個元素，這次遞歸的時間開銷的上界為 \(T(\dfrac{7n}{10})\)。

綜上，我們可以列出這樣的不等式：

\[ T(n) \leq T(\dfrac{n}{5}) + T(\dfrac{7n}{10}) + O(n) \]

假設 \(T(n) = O(n)\) 在問題規模足夠小時成立。根據定義，此時有 \(T(n) \leq cn\)，其中 \(c\) 為一正常數。將不等式右邊的所有 \(T(n)\) 進行代換：

\[ \begin{aligned} T(n) & \leq T(\dfrac{n}{5}) + T(\dfrac{7n}{10}) + O(n)\\ & \leq \dfrac{cn}{5} + \dfrac{7cn}{10} + O(n)\\ & \leq \dfrac{9cn}{10} + O(n)\\ & = O(n) \end{aligned} \]

到這裏我們就證明了，該算法在最壞情況下也具有 \(O(n)\) 的時間複雜度。

參考資料與註釋

本页面最近更新：，更新历史
发现错误？想一起完善？在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用