摘要訊息 : 有沒有一種排序演算法, 在平均情況下可以很快?

0. 前言

分而治之演算法 (《分而治之演算法》) 所產生的合併排序法 (《【演算法】合併排序法 (Merge Sort)》) 實際上是基於有序序列合併的排序法, 這也是這個排序演算法名稱的由來. 其實還有一種名為快速排序法的排序演算法使用的也是分而治之的思想.

本篇文章中, 我們主要討論的是升序的快速排序法, 也就是從小到大對元素進行排序. 對於降序的情況, 類似可得.

更新紀錄 :

• 2022 年 6 月 2 日進行第一次更新和修正.

1. 找到第 $i$ 小的元素

對於集合 $\mathscr {S} = \left \{ e_{1}, e_{2}, ..., e_{n} \right \}$ 和給定的 $i$ ($1 \leq i \leq n$), 可以找到 $\mathscr {S}$ 中第 $i$ 小的元素並且和 $e_{i}$ 進行交換, 使得第 $i$ 小的元素 $e$ 位於集合 $\mathscr {S}$ 中第 $i$ 個位置, 即 $e_{i} = e$. 接著, 我們將 $\mathscr {S}$ 從第 $i$ 個位置一分為二, 分為 $S_{\mathrm {L}} = \left \{ e_{1}, e_{2}, ..., e_{i - 1} \right \}$ 和 $\mathscr {S}_{\mathrm {R}} = \left \{ e_{i + 1}, e_{i + 2}, ..., e_{n} \right \}$, 再利用類似的方法. 如果最終總能夠使得對於集合 $\mathscr {S}$ 來說, 第 $i$ 小的元素在第 $i$ 個位置上, 那麼集合 $\mathscr {S}$ 便有序了.

我們僅僅滿足於找到第 $i$ 小的元素嗎? 不是的. 將第 $i$ 小的元素放置到第 $i$ 個位置, 然後將原集合按第 $i$ 個位置一分為二這個粗略描述是不正確的. 因為雖然第 $i$ 小的元素被放到了正確的位置, 但是如果第 $i + 1$ 小的元素被放入了第 $i$ 小的元素的左側, 那麼即使 $\mathscr {S}_{\mathrm {L}}$ 和 $\mathscr {S}_{\mathrm {R}}$ 有序, 能保證 $\mathscr {S}$ 有序嗎? 不能. 我們能保證的只是第 $i$ 個位置左右兩側有序. 因此, 我們不僅僅滿足於找到第 $i$ 小的元素 $e$, 還要做到比 $e$ 小的元素放在 $e$ 的左側, 比 $e$ 大的元素在 $e$ 的右側. 那麼此時, 如果 $\mathscr {S}_{\mathrm {L}}$ 和 $\mathscr {S}_{\mathrm {R}}$ 有序, 必定會有 $\mathscr {S}$ 有序.

我們可以看到, 利用這樣的方法, 我們甚至都不需要進行合併, 一分為二之後根據分治策略找到第 $i$ 小的元素即可. 最終, 任取 $k \in [1, n]$, 第 $k$ 個位置必定是第 $k$ 小的, 也就沒有合併的必要了.

現在的問題是一分為二到什麼程度. 在合併排序法中, 我們分到一個小集合中元素至多為兩個結束, 但是在找到第 $i$ 小的元素中, 我們分到小集合中僅有一個元素才結束. 這個時候, 我們不需要進行任何操作, 因為只有一個元素的子集合本身就是有序的.

這樣, 對如何找到第 $i$ 小的元素, 我們就有了基本的思路. 首先我們要確定的是, 我們沒有辦法直接從集合中找到第 $i$ 的元素, 也不能通過掃描集合這種方式, 因為掃描集合找到第 $i$ 小的元素是插入排序法的做法. 因此, 我們應該從集合中選出一個元素, 然後確定這個元素在什麼位置上, 比這個元素大的都要求在這個元素的右邊, 比這個元素小的都要求在這個元素的左邊. 然後以該元素所在位置為基礎, 一分為二. 也就是說, 我們將思路轉變了. 之前是以 $i$ 為基礎, 找到第 $i$ 小的元素.

定義 1. 從集合 $\mathscr {S} = \left \{ e_{1}, e_{2}, ..., e_{n} \right \}$ 中任取一個元素 $e_{k}$, 確定 $e_{k}$ 在集合中第 $i$ 小並和 $e_{i}$ 進行交換, 我們稱這樣的 $e_{k}$ 為支點 (pivot). 其中, $i, k = 1, 2, ..., n$.

現在, 我們是選出一個元素, 確定其是第 $i$ 小, 然後安排到 $e_{i}$ 這個位置上去. 為了方便起見, 我們假設選取 $e_{1}$, 即支點為 $e_{1}$, 令 $p = e_{1}$. 那麼原本集合中 $e_{1}$ 這個位置便空了出來. 令 $l = 1$ 且 $r = n$, 我們有 :

1. 逐一減小 $r$, 找到一 $e_{r}$ 滿足 $e_{r} < p$, 此時令 $e_{l} = e_{r}$ 並令 $l$ 加一;
2. 逐一增加 $l$, 找到一 $e_{l}$ 滿足 $e_{l} > p$, 此時令 $e_{r} = e_{l}$ 並令 $r$ 減一;
3. 回到第一步, 並且不斷重複第一步和第二步, 直到 $l = r$ 時停止. 此時 $e_{l}$ 便是 $p$ 應該安排的位置, 即元素 $p$ 在原集合 $\mathscr {S}$ 中第 $l$ 小. 因此, 我們令 $e_{l} = p$;
4. 以 $e_{l}$ 為基準, 將序列劃分為 $\mathscr {S}_{\mathrm {L}} = \left \{ e_{1}, e_{2}, ..., e_{l - 1} \right \}$ 和 $\mathscr {S}_{\mathrm {R}} = \left \{ e_{l + 1}, e_{l + 2}, ..., e_{n} \right \}$;
5. 遞迴地對 $\mathscr {S}_{\mathrm {L}}$ 和 $\mathscr {S}_{\mathrm {R}}$ 應用類似的過程;
6. 最終集合 $\mathscr {S}$ 有序.

我們稱 Algorithm 1 為快速排序法 (quick sort).

例題 1. 設 $\mathscr {S} = \left \{ 2, 9, 4, 2, 9, 7, 3 \right \}$, 利用 Algorithm 1 對 $\mathscr {S}$ 進行排序.

$解$ :

一開始, 令 $l = 1$, $r = \mathop {\mathrm {card}} {\mathscr {S}} = 7$, $p = 2$ 且 $m = 0$. 總體來說, 我們有

因為 $m = 0$, 所以我們向左移動 $r$. 當 $r = 4$ 時, 有 $2 < 2$ 不成立, 故令 $e_{l} = e_{r} = 2$, 並更新 $l = 2$ 且 $m = 1$. 於是有

因為 $m = 1$, 所以我們向右移動 $l$. 但是已經有 $9 < 2$ 不成立, 故令 $e_{r} = e_{l} = 9$, 並更新 $r = 3$ 且 $m = 0$. 於是有

現在又有 $m = 0$, 但是向左移動 $r$ 的過程中產生了 $l = r$ 的情形. 這個時候停止移動 $r$, 令 $e_{l} = p = 2$. 以 $e_{l}$ 這個元素為基礎, 將集合分割為 $\left \{ 2 \right \}$ 和 $\left \{ 4, 9, 9, 7, 3 \right \}$. 接著, 我們準備對左側的子集進行快速排序法的時候, 發現它只有一個元素, 因此它本身就是有序的. 為此, 前兩個元素已經有序. 那麼我們只需要處理右邊的子集即可.

令 $l = 3$, $r = 7$, $p = 4$ 且 $m = 0$. 我們打算向左移動 $r$ 的時候發現 $4 < 3$ 不成立, 所以令 $e_{l} = e_{r} = 4$, 更新 $l = 4$ 且 $m = 1$.

向右移動 $l$ 的時候發現 $9 < 4$ 不成立, 因此令 $e_{r} = e_{l} = 9$, 更新 $r = 6$ 且 $m = 0$.

現在 $m = 0$, 因此需要向左移動 $r$. 最終會有 $l = r$ 成立. 此時, 我們令 $e_{l} = 4$. 此時以 $e_{l}$ 將 $\left \{ 3, 4, 9, 7, 9 \right \}$ 分成 $\left \{ 3 \right \}$ 和 $\left \{ 9, 7, 9 \right \}$. 左側子集只有一個元素, 因此是有序的. 我們只需要考慮右側子集.

令 $l = 3$, $r = 7$, $p = 4$ 且 $m = 0$. 我們打算向左移動 $r$ 的時候發現 $4 < 3$ 不成立, 所以令 $e_{l} = e_{r} = 4$, 更新 $l = 4$ 且 $m = 1$.

由於 $9 < 9$ 不成立, 所以令 $e_{l} = e_{r} = 9$, 更新 $l = 6$ 且 $m = 1$.

向右移動 $l$ 直到 $l = r$, 令 $e_{l} = p = 9$. 此時以 $e_{l}$ 將 $\left \{ 9, 7, 9 \right \}$ 分成 $\left \{ 9, 7 \right \}$ 和 $\emptyset$. 右側子集沒有元素. 我們只需要考慮左側子集.

令 $l = 5$, $r = 6$, $p = 9$ 且 $m = 0$. 由於 $9 < 7$ 不成立, 因此令 $e_{l} = e_{r} = 9$, 並更新 $l = 6$ 且 $m = 1$.

此時, 由於 $l = r$, 所以令 $e_{l} = 9$. 以 $e_{l}$ 將 $\left \{ 7, 9 \right \}$ 分成 $\left \{ 7 \right \}$ 和 $\emptyset$. 左側子集只有一個元素, 因此有序; 右側子集是空的, 不需要任何處理. 所以快速排序法完成.

最終, $\mathscr {S} = \left \{ 2, 2, 3, 4, 7, 9, 9 \right \}$ 有序.

$\blacksquare$

2. 支點取法

Algorithm 1 預設將 $e_{1}$ 作為支點. 我們當然也可以將 $e_{n}$ 作為支點, 這個時候我們只需要修改 Algorithm 1 中第三行為 $m \leftarrow 1$ 即可.

對於非兩端元素作為支點的取法, 一般來說我們都會讓該元素和兩端元素中的一個作交換. 例如我們要將 $e_{i}$ 作為支點 ($i \neq 1$ 且 $i \neq n$), 那麼我們只需要讓 $e_{i}$ 和 $e_{1}$ (或者 $e_{n}$) 作交換, 然後將 $e_{1}$ (或者 $e_{n}$) 作為支點即可.

3. 穩定性分析

快速排序法並不是穩定的排序法, 而且在 Algorithm 1 下也沒有辦法對其進行更改使得快速排序法變成穩定的排序法. 設 $\mathscr {S} = \left \{ e_{1}, e_{2}, ..., e_{i}, e_{i + 1}, e_{i + 2}, ..., e_{n} \right \}$ 滿足 $e_{1} = e_{i}$. 當 $r = i$ 時, $e_{1} < e_{r}$ 並無法滿足, 於是 $e_{l}$ 被 $e_{r}$ 指派. 指派完成之後, $l$ 的值會增加一. 也就是說, 不論之後怎麼樣, 原集合中的 $e_{i}$ 永遠都在原集合中的 $e_{1}$ 的左側. 也就是說, 排序的結果是不穩定的.

另一方面, 是否可以通過更改 Algorithm 1 中第七行和第十八行中的 $p < e_{r}$ 和 $e_{l} < p$ 為 $p \leq e_{r}$ 和 $e_{l} \leq p$ 來保持其穩定性呢? 例如就像《【演算法】合併排序法 (Merge Sort)》中的 Algorithm 1 那樣, 把 $\leq$ 改為 $<$ 就可以維持合併排序法地穩定性. 很遺憾, 答案是不能. 考慮 $\left \{ e_{1}, e_{2}, ..., e_{n} \right \}$, 其滿足 $e_{1} = e_{2}$ 且 $e_{n} < e_{1}$. 那麼根據修改之後的 Algorithm 1', 一開始令 $l = 1$, $r = n$, $p = e_{1}$ 和 $m = 0$. 由於 $m = 0$, 因此要向左移動 $r$ 調整元素. 由於 $p \leq e_{n}$ 不成立, 因此令 $e_{1} = e_{n}$, 並更新 $l = 2$ 且 $m = 1$. 接下來因為 $m = 1$, 要向右移動 $l$ 調整元素. 此時, $e_{l} = e_{2} = 3$, 這個 $3$ 在排序之後, 如果要維持穩定性, 就必須在 $p$ 之後. 然而, 由於 $e_{l} \leq p$ 成立, 因此 $l$ 會繼續增加. 也就是說, 不論之後元素怎麼調整, $p$ 一定會被安排在原 $e_{2}$ 之後. 此時, 排序的結果仍然是不穩定的.

綜上所述, 不論是否更改支點的選區方案, 是否更改比較方案, Algorithm 1 中的快速排序法總是不穩定的.

那麼不禁要問, 是否存在一種方案, 使得快速排序法變成穩定的排序演算法呢? 額外配置一塊空間記錄原集合中的元素順序即可. 但是這種方案通常不採用. 一般來說, 對排序的穩定性有要求的話, 通常會選擇合併排序法.

4. 複雜度分析

快速排序法和合併排序法一樣, 採用了分而治之演算法. 所以, 它的空間複雜度和合併排序法是一樣的 (見《【演算法】合併排序法 (Merge Sort)》第 3.2 節), 為 $\Theta(\log {n})$.

由於快速排序法使用了分而治之演算法, 所以可以根據分而治之演算法時間複雜度分析的方法 (參考《分而治之演算法》第 3.2 節) 對快速排序法的時間複雜度進行分析. 根據 Algorithm 1 的描述, 當元素數量滿足 $n \leq 1$ 時, 根本不需要進行任何操作; 當元素數量滿足 $n > 1$ 時, 假設支點元素在原集合 $\mathscr {S}$ 中第 $i$ 小, 那麼當支點元素被放置在 $e_{i}$ 這個位置之後, 我們以 $e_{i}$ 這個元素為基準, 將整個集合劃分為 $\mathscr {S}_{\mathrm {L}} = \left \{ e_{1}, e_{2}, ..., e_{i - 1} \right \}$ 和 $\mathscr {S}_{\mathrm {R}} = \left \{ e_{i + 1}, e_{i + 2}, ..., e_{n} \right \}$, 然後分別對 $\mathscr {S}_{\mathrm {L}}$ 和 $\mathscr {S}_{\mathrm {R}}$ 這兩個子集遞迴地使用快速排序法. 最終, 快速排序法的時間複雜度可以表示為 $\displaystyle {T(n) = \begin {cases} 0 & {n \leq 1} \\ T(i) + T(n - i - 1) + D(n) + C(n) &{n > 1}. \end {cases}}$ 由於快速排序法不需要合併, 因此 $C(n) = 0$. 另外, 根據支點調整元素, 使得左側元素都小於支點元素, 右側元素都大於支點元素, 需要尋訪整個序列. 因此, $D(n) = \Theta(n)$. 最終, 快速排序法的時間複雜度可以表示為 $\displaystyle {T(n) = \begin {cases} 0 & {n \leq 1} \\ T(i) + T(n - i - 1) + \Theta(n) &{n > 1}. \end {cases}}$ 我們當然可以通過解這個遞迴方程式得到快速排序法的時間複雜度, 但是由於 $i$ 具有不確定性, 所以解這個遞迴方程式存在一定的困難. 但是, 我們仍然可以通過另一種方式證明快速排序法的時間複雜度. 為了得到快速排序法的時間複雜度, 我們需要引入一些引理和結論.

引理 1. 基於比較的排序演算法的時間複雜度下界為 $\Omega(n\log {n})$.

$證明$ :

根據《複雜度下界》第 2 節, 我們知道基於比較的排序演算法最壞情況下都要進行 $\Omega(n\log {n})$ 次比較, 因此時間複雜度的下界是 $\Omega(n\log {n})$.

$\blacksquare$

結論 1. 設函數 $f(x) = x \ln {x}$, 當 $x \geq 1$ 時, $f(x)$ 單調增加.

$證明$ :

通過求導數可知, $f'(x) = \ln {x} + 1$. 令 $f'(x) = 0$, 即 $\ln {x} + 1 = 0$ 可解得 $x = \frac {1}{e}$. 當 $x \in \left ( 0, \frac {1}{e} \right ]$ 時, $f'(x) < 0$; 當 $x \in \left [ \frac {1}{e}, + \infty \right )$ 時, $f'(x) > 0$. 因此, $f(x)$ 在 $\left ( 0, \frac {1}{e} \right )$ 上單調減少, 在 $x \in \left [ \frac {1}{e}, + \infty \right )$ 時單調增加.

$\blacksquare$

結論 2. $\int_{2}^{m}x \ln {x}dx < \frac {1}{2}m^{2} \ln {m} - \frac {m^{2}}{4}$.

$證明$ :

我們使用分部積分法, 可以得到 $\displaystyle {\begin {aligned} \int_{2}^{m} x\ln {x} \mathrm {d}{x} &= \left . \frac {1}{2}x^{2} \ln {x} \right |_{2}^{m} - \frac {1}{2}\int_{2}^{m} x^{2}\frac {1}{x} \mathrm {d}{x} \\ &= \left . \frac {1}{2}x^{2}\ln {x} \right |_{2}^{m} - \left . \frac {1}{4}x^{2} \right |_{2}^{m} \\ &= \frac {1}{2}m^{2}\ln {m} - \frac {m^{2}}{4} - 2\ln {2} + 1. \end {aligned}}$ 由於 $1 - 2\ln {2} < 0$, 故 $\int_{2}^{m} x\ln {x} \mathrm {d}{x} < \frac {1}{2}m^{2}\ln {m} - \frac {m^{2}}{4}$.

$\blacksquare$

斷言 1. 以 Algorithm 1 驅動的快速排序法的平均時間複雜度為 $\Theta(n\log {n})$.

$證明$ :

令 $T(n)$ 表示對 $n$ 個元素的序列進行快速排序法的平均時間. 當 $n \leq 1$ 時, $T(n) \leq d$. 其中, $d$ 為常數. 當 $n > 1$ 時, 記 $i$ 為左側子集元素數量, 因此右側子集元素的數量為 $n - i - 1$. 故左側子集的平均排序時間為 $T(i)$, 右側子集的平均排序時間為 $T(n - i - 1)$. 設分割序列的時間為 $cn$, 其中 $c$ 為常數. 由於 $i$ 可以從 $0$ 到 $n - 1$ 任意取值, 不妨設取任意值的機率相等, 那麼我們可以得到方程式組 $\displaystyle {\begin {cases} T(n) = T(0) + T(n - 1) + cn \\ T(n) = T(1) + T(n - 2) + cn \\ T(n) = T(2) + T(n - 2) + cn \\ \vdots \\ T(n) = T(n - 1) + T(0) + cn \end {cases}}$ 將左右兩側相加可以得到 $\displaystyle {nT(n) = \sum \limits_{i = 0}^{n - 1}\big ( T(i) + T(n - i - 1) \big ) + n \cdot cn}.$ 等式兩側同乘以 $\frac {1}{n}$ 可以得到 $\displaystyle {T(n) = \frac {1}{n}\sum \limits_{i = 0}^{n - 1}\big ( T(i) + T(n - i - 1) \big ) + cn}.$ 繼續進行演算, 則有 $\displaystyle {\begin {aligned} T(n) &= \frac {1}{n}\sum \limits_{i = 0}^{n - 1}\big ( T(i) + T(n - i - 1) \big ) + cn \\ &= \frac {1}{n} \sum \limits_{i = 0}^{n - 1}T(i) + \frac {1}{n}\sum \limits_{i = 0}^{n - 1}T(n - i - 1) + cn \\ &= \frac {1}{n}\sum \limits_{i = 0}^{n - 1}T(i) + T(n - 1) + T(n - 2) + ... + T(1) + T(0) + cn \\ &= \frac {1}{n} \bigg ( T(0) + T(1) + ... + T(n - 2) + T(n - 1) + \\ &\ \ \ \ \ \ \ \ T(n - 1) + T(n - 2) + ... + T(1) + T(0) \bigg ) + cn \\ &= \frac {2}{n}\sum \limits_{i = 0}^{n - 1}T(i) + cn \\ &= \frac {2}{n}\sum \limits_{i = 2}^{n - 1}T(i) + \frac {2}{n}T(0) + \frac {2}{n}T(1) + cn \\ &\leq \frac {2}{n}\sum \limits_{i = 2}^{n - 1}T(i) + cn + \frac {4}{n}d. \end {aligned}}$ 接著, 我們使用歸納法來證明 $T(n) \leq kn\ln {n}$. 其中, $n > 1, k = 2(c + d)$.

當 $n = 2$ 時, $\sum \limits_{i = 2}^{n - 1}T(i)$ 為零, 因此 $T(2) \leq 2c + 2d = k \leq 2\ln {2}k$; 不妨設 $n < m$ 時, 都有 $T(n) \leq kn\ln {n}$ 成立; 那麼當 $n = m$ 時, 有 $\displaystyle {\begin {aligned} T(m) &\leq \frac {2}{m}\sum \limits_{i = 2}^{m - 1}T(i) + cm + \frac {4}{m}d \\ &= \frac {2}{m}T(2) + \frac {2}{m}T(3) + ... + \frac {2}{m}T(m - 2) + \frac {2}{m}T(m - 1) + \frac {4}{m}d + cm + \frac {4}{m}d. \end {aligned}}$ 由於當 $n < m$ 時, 有 $T(n) \leq kn\ln {n}$ 成立, 故有 $\displaystyle {\begin {aligned} T(m) &\leq \frac {2}{m}T(2) + \frac {2}{m}T(3) + ... + \frac {2}{m}T(m - 2) + \frac {2}{m}T(m - 1) + \frac {4}{m}d + cm + \frac {4}{m}d \\ &\leq \frac {2}{m}k \cdot 2\ln {2} + \frac {2}{m}k \cdot 3\ln {3} + ... + \frac {2}{m}k \cdot (m - 2)\ln {(m - 2)} + \\ &\ \ \ \ \ \frac {2}{m}k \cdot (m - 1)\ln {(m - 1)} + cm + \frac {4}{m}d \\ &= \frac {2}{m}k\sum \limits_{i = 2}^{m - 1}i\ln {i} + cm + \frac {4}{m}d. \end {aligned}}$ 結合結論 1 和結論 2 可知, $\displaystyle {\int_{2}^{m - 1} x\ln {x} \mathrm {d}{x} < \int_{2}^{m} x\ln {x} \mathrm {d}{x} < \frac {1}{2}m^{2}\ln {m} - \frac {m^{2}}{4}}.$ 所以 $\displaystyle {\begin {aligned} T(m) &\leq \frac {2}{m}k\sum \limits_{i = 2}^{m - 1}i\ln {i} + cm + \frac {4}{m}d \\ &< \frac {2}{m}k\int_{2}^{m} i\ln {i} \mathrm {d}{i} + cm + \frac {4}{m}d \\ &< \frac {2}{m}k\left ( \frac {1}{2}m^{2}\ln {m} - \frac {m^{2}}{4} \right ) + cm + \frac {4}{m}d \\ &= km \cdot \ln {m} - \frac {m}{2}k + cm + \frac {4}{m}d \\ &< km\ln {m}. \end {aligned}}$ 因此, 當 $n = m$ 時, 也有 $T(n) \leq kn\ln {n}$.

綜上所述, $T(n) = O(n\log {n})$. 結合引理 1, 最終有 $T(n) = \Theta(n\log {n})$.

$\blacksquare$

5. 特殊情形

快速排序法以快著稱, 幾乎所有程式設計語言的標準程式庫都會引入快速排序演算法. 例如 C 中來自標頭檔 <stdlib.h> 的 qsort, C++ 中來自標頭檔 <algorithm> 的 std::sort. 然而它也存在一些特殊情形需要我們進一步進行討論.

5.1 運氣不好

若集合滿足 $\mathscr {S} = \left \{ e_{1}, e_{2}, ..., e_{n} : e_{1} \geq e_{2} \geq ... \geq e_{n} \right \}$, 那麼對 $\mathscr {S}$ 使用快速排序法的效能會非常差. 大家可以自行構造一個倒序的集合 (元素從大到小排列), 然後對其使用快速排序法嘗試一下. 如果我們選擇集合的第一個元素作為支點, 那麼在當 $r$ 開始向左移動的時候, 立馬就會進行一次交換. 接下來是 $l$ 向右移動, 一直到與 $r$ 相遇. 這個最大的元素就會被安排到集合的最後一個位置. 這裡總共進行了 $n - 1$ 次比較. 接下來以該元素為基礎進行劃分, 左側子集有 $n - 1$ 個元素, 右側子集沒有元素. 現在在左側序列中, 由於原序列中最後一個元素被交換到了 $e_{1}$ 的位置, 因此 $e_{1}$ 便是最小的. 雖然不需要進行交換, 但是需要進行 $n - 2$ 次比較. 以該元素為基準對集合一分為二, 剩下來的 $\left \{ e_{2}, e_{3}, ..., e_{n - 1} \right \}$ 又遇到了從大到小排列的情形. 總共的比較次數是 $\displaystyle {(n - 1) + (n - 2) + ... + 2 + 1 = \frac {n(n - 1)}{2}}.$ 根據《漸近分析基礎》中的定理 6, 即 Θ 記法比率定理, 這個時候快速排序法的時間複雜度便是 $\Theta(n^{2})$ 而不是斷言 1 中所說的 $\Theta(n\log {n})$.

所以, 斷言 1 中指出了 $\Theta(n\log {n})$ 是快速排序法的平均時間複雜度. 除了上面這個情形之外, 如果每一次支點元素都運氣不太好地選擇了最大的元素或者最小的元素, 又或者集合中所有元素都相同, 那麼此時快速排序法的時間複雜度都是 $\Theta(n^{2})$.

為此, 如何選擇支點非常重要. 為了盡可能避免 (無法完全避免) 最壞的情形, 支點的選擇有其它一些方法 :

• 取序列中間的元素;
• 取第一個元素, 中間元素和最後一個元素的中位數;
• 取序列的中位數;
• 隨機取序列中的任意一個元素;
• ...

我們特別指出, 如果集合中的全部元素都相同, 那麼不論支點如何選擇, 最終都會遇到最壞情形. 不過值得慶幸的是, 最壞的情形並不多見, 而且這些選擇方法都會產生額外的消耗. 所以一般來說, 我們仍然會採用 Algorithm 1 中的做法, 只有預先知道了高度可能遇見最壞情形, 我們才對支點的選擇進行特殊化處理.

5.2 大量元素重複

第 5.1 節中我們提到, 對全部元素都相同的集合使用快速排序法會產生最壞的情形. 這種情況並不多見, 不過我們更可能會遇到集合中存在大量元素重複的情形. 如果集合中存在大量元素重複, 快速排序法的時間複雜度就會變成 $O(n^{2})$ 而不是嚴格的 $\Theta(n\log {n})$ 或者 $\Theta(n^{2})$. 原理和第 5.1 節中的原因是差不多的. 如果需要排序的集合經常會存在大量元素重複的情形 (甚至有時候全部元素都是相同的情形), 那麼我們是可以改進經典的快速排序法. 改進的方案就是一分為三, 而不是繼續保持一分為二. 在 Algorithm 1 中, 我們將集合以支點所在位置為中心, 劃分為支點左側子集, 支點右側子集. 在一分為三的方案中, 我們以支點所在的位置為基礎, 劃分為小於支點元素的左側子集, 等於支點元素的中間子集和大於支點元素的右側子集.

第一種方案比較簡單, 設 $c$, $c_{1}$ 和 $c_{2}$ 是分割點. 對於存在大量重複元素的集合 $\mathscr {S} = \left \{ e_{1}, e_{2}, ..., e_{n} \right \}$, 在進行快速排序的時候, 我們只要保證 $\left \{ e_{1}, e_{2}, ..., e_{c_{1} - 1} \right \}$ 中的元素小於支點元素元素, $\left \{ e_{c_{2} + 1}, e_{c_{2} + 2}, ..., e_{n} \right \}$ 中的元素大於支點元素, 而 $\left \{ e_{c_{1}}, e_{c_{1} + 1}, ..., e_{c - 1} \right \}$ 中的元素等於支點元素. 那麼接下來, 我們只需要處理 $\left \{ e_{c}, e_{c + 1}, ..., e_{c_{2}} \right \}$ 中的元素即可.

設支點元素為 $p$. 對於 $e_{c}$, 如果

• $e_{c} < p$, 那麼交換 $e_{c_{1}}$ 和 $e_{c}$ 之後, 令 $c_{1}$ 和 $c$ 同時加一;
• $e_{c} = p$, 令 $c$ 增加一;
• $e_{c} > p$, 那麼交換 $e_{c_{2}}$ 和 $e_{c}$ 之後, 令 $c_{2}$ 減去一.

以 Figure 5 為例. 如果遇到 $e_{c} < p$ 的情形, 相當於 $c_{1}$ 這個分割點向後移動了. 因為本來 $e_{c_{1}}$ 儲存著和 $p$ 相等的元素, 它被移動到 $e_{c}$ 這個位置之後, 相等區域也需要向後擴容, 也就是 $c$ 也需要加一. 如果遇到 $e_{c} = p$ 的情形, 那麼只需要擴容相等區域, 即讓 $c$ 加一即可. 如果遇到 $e_{c} > p$ 的情形, 那麼 $e_{c}$ 應該被放入大於支點元素的區域, 那麼就需要和 $e_{c_{2}}$ 作交換, 之後讓大於支點元素區域擴容, 即 $c_{2}$ 向前移動一個位置. 當然, 一開始, $c_{1} = 1$, $c_{2} = n$ 且 $c = 2$.

使用這種方案在存在大量元素重複的情況下, 對快速排序法的效能提升非常有效. 然而, 一旦面對通用的情形, 這種方案相比於 Algorithm 1 中的演算法, 多了很多次交換. 所以, 在通用情形下, 這個方案並不流行. 還有一種方案是將集合中等於支點的元素放在兩端 :

當 $c_{2} = c_{3}$ 時, 需要把兩端相等的元素進行合併. 這種方案交換的次數比第一個方案在平均情況下要少一些, 所以採用得也多一些.

5.3 幾乎有序

如果給定的集合 $\mathscr {S}$ 是幾乎有序的, 那麼除了採用改變支點選擇方案這個辦法之外, 還可以借助插入排序法 (《【演算法】插入排序法 (Insertion Sort)》). 但是要注意的是, 我們並不是對整個集合直接使用插入排序法. 一開始, 我們仍然對整個集合採用快速排序法, 當劃分之後的子集元素數量少於一定規模的時候, 我們就可以採用插入排序法. 對於幾乎有序的小規模集合, 插入排序法的效能是比快速排序法要快的.

6. 實作

Code 1. 快速排序法
void quick_sort(int *arr, int size) {
    auto left {0};
    auto right {size - 1};
    auto pivot {arr[0]};
    auto move_right {true};
    while(true) {
        if(move_right) {
            while(left < right and pivot < arr[right]) {
                --right;
            }
            if(left < right) {
                arr[left++] = arr[right];
                move_right = false;
                continue;
            }
        }else {
            while(left < right and arr[left] < pivot) {
                ++left;
            }
            if(left < right) {
                arr[right--] = arr[left];
                move_right = true;
                continue;
            }
        }
        arr[left] = pivot;
        if(left > 1) {
            quick_sort(arr, left);
        }
        if(size - left - 1 > 1) {
            quick_sort(arr + (left + 1), size - left - 1);
        }
        break;
    }
}

Code 1 中的快速排序法是基於 Algorithm 1 的, 沒有引入什麼優化. 對於泛型版本的實作, 大家可以參考我的 GitHub : https://github.com/Jonny0201/data_structure/blob/master/data_structure/algorithm.hpp, 搜尋 quick_sort 即可.