分而治之與排序 – 快速排序法 (Quick Sort)

使用分而治之演算法的思想, 可以實現另外一種排序法, 即快速排序法. 在快速排序法中, 首先將序列分為三個部分 : 左段、支點和右段. 支點是來自序列中的某一個元素, 其取法包括但不限於 :

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

在選取支點之後, 要求左段元素都不大於支點元素, 右段元素都不小於支點. 初始時, 左段和右段中的元素都是亂序的. 我們進行雙邊尋訪, 對於左段的元素, 我們向右進行尋訪; 對於右段的元素, 我們向左進行尋訪. 首先提取支點中的元素, 由於這個原因, 在進行尋訪時序列中總會有一個空的位置. 從左段元素開始向右進行尋訪, 找到一個元素比支點元素要大, 然後將這個元素移動到空的位置; 然後交換尋訪順序, 對右段元素向左進行尋訪尋訪, 找到一個元素比支點元素要小, 將其移動到空的位置中. 此時, 可能會出現一種比較特殊的情況, 即左右兩側進行尋訪時, 停留在了同一個位置. 這個時候直接結束本次尋訪, 然後將原支點元素放入這個位置 (因為這個位置總是不存在元素, 具體可以觀察下面的圖象演示). 如果並沒有同時停留在一個位置, 那麼交替至左側繼續向右尋訪, 然後交替至右側繼續向左尋訪. 重複這樣的步驟知道左右兩側停留在同一個位置. 此時, 將支點元素放回到這個位置, 這個位置就是支點元素最終所在的位置. 以這個位置為劃分界線, 將序列分成三段, 左段、支點和右段, 對左右兩端遞迴地使用快速排序法即可. 當一次尋訪之後, 通過交換, 左段中大於支點的元素會被交換到右段, 右段中小於支點的元素會被交換到左段, 最終可以得到一個有序序列. 和合併排序法不同, 快速排序法在排序完成之後, 序列已經有序, 而不需要合併

我們使用圖像來演示快速排序法. 不論序列順序如何, 我們統一選取最後一個元素作為支點. 初始時 :

提取 1 至支點進行臨時存儲, 將 left 向右移動尋找第一個大於支點 1 的元素. 我們發現, 7 已經是一個大於支點 1 的元素, 因此把 7 放到序列中空的位置, 即 right 目前所在的位置 :

接著輪到 right 向左側進行尋訪, 以便找到第一個小於支點 1 的元素. 向左側尋訪兩個元素之後, right 會發現 0 是一個小於支點 1 的元素, 因此將其交換至目前序列空的位置, 即 left 目前所處的位置 :

現在輪到 left 向右尋訪, 目前 left 所對應的元素 2 大於支點元素 1, 因此將其放入 right 所對應的空位中 :

現在 right 和 left 相遇, 因此將之前提取的支點元素放入到目前序列的空位置中 :

此時, 序列從原支點 1 對應的位置開始劃分, 將序列分為左段和右段. 由於左段有且唯有一個元素, 已經有序, 因此我們接下來僅演示右段的子序列 :

首先對 left 向右移動, 一直移動的過程中, left 找不到比支點元素 7 大的元素, 因此直接將支點元素 7 放入 right 對應的空位置中, 此時序列再次被劃分 :

令 left 向右移動, 找到元素 6 要比支點元素 5 大, 因此將 6 放入 right 對應的空位中 :

此時, left 和 right 相遇, 將支點元素支點元素 5 放入這個空位中即可. 與此同時, 序列繼續被劃分 :

雖然序列已經有序, 但是電腦並不知道, 所以還會繼續進行遞迴. 接下來就不再演示
現在, 我們來分析快速排序法的時間複雜度. 設 $n$ 時序列中元素數量, 當 $n = 1$ 時, 序列本身已經有序, 因此其使用的時間是常數級別, 故 $T(1) = \Theta(1)$ . 當 $n > 1$ 時, 設 $i$ 為左段元素中具有的數量, 則右段元素中具有 $n - i - 1$ 個. 每一次尋訪都使得左段中的元素符合要求, 需要使用 $\Theta(n)$ 的時長. 之前已經提到, 快速排序法不需要合併, 因此合併只是函式的終結, 用時也是常數級別的, 即 $\Theta(1)$

通過上述分析, 我們知道, $D(n) = \Theta(n), C(n) = \Theta(1)$ . 因此, 快速排序法的時間複雜度遞迴方程式為 :

$T(n) = \begin {cases} \Theta(1) & {n = 1} \\ T(i) + T(n - i - 1) + \Theta(n) &{n > 1} \end {cases}$

解這個遞迴方程式可以得到 $T(n) = \Theta(n \log {n})$ . 不過, 我們可以從另外一個角度來證明快速排序法的時間複雜度為 $\Theta(n \log {n})$ . 為此, 我們需要引入兩個結論和一個引理 :

結論 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 (0, \frac {1}{e}]$ 時, $f'(x) < 0$ ; 當 $x \in [\frac {1}{e}, + \infty)$ 時, $f'(x) > 0$ . 因此, $f(x)$ 在 $(0, \frac {1}{e})$ 上單調減少, 在 $x \in [\frac {1}{e}, + \infty)$ 時單調增加

$\blacksquare$

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

$證$ :

我們使用分部積分法, 可以得到

$\begin {aligned} \int_{2}^{m}x \ln {x}dx &= (\frac {1}{2}x^{2} \ln {x})_{2}^{m} - \frac {1}{2} \int_{2}^{m}x^{2} \frac {1}{x}dx \\ &= (\frac {1}{2}x^{2} \ln {x})_{2}^{m} - \frac {1}{4}(x^{2})_{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}dx < \frac {1}{2}m^{2} \ln {m} - \frac {m^{2}}{4}$
$\blacksquare$

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

這個引理我們已經在文章《複雜度下限》中進行了證明

$\blacksquare$

定理 1. 快速排序法的平均時間複雜度為 $\Theta(n \log {n})$ . 其中, $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$ 任意取值, 概率相等, 故有遞迴不等式 :

$\begin {aligned} T(n) &\leq \frac {1}{n} \sum_{i = 0}^{n - 1}T(i) + T(n - i - 1) + cn \\ &\leq \frac {2}{n} \sum_{i = 0}^{n - 1}T(i) + cn \\ &\leq \frac {2}{n}\sum_{i = 2}^{n - 1}T(i) + \frac {4}{n}d + cn \end {aligned}$
接著, 我們使用歸納法來證明 $T(n) \leq kn \ln {n}$ . 其中, $n > 1, k = 2(c + d)$
當 $n = 2$ 時, $T(2) \leq 2c + 2d \leq kn \ln {2}$
不妨設 $n < m$ 時, 都有 $T(n) \leq kn \ln {n}$
當 $n = m$ 時, 有

$T(m) \leq cn + \frac {4}{m}d + \frac {2}{m}\sum_{i = 2}^{m - 1}T(i) \leq cm + \frac {4}{m}d + \frac {2}{m}\sum_{i = 2}^{m - 1}i \ln{i}$
由 結論 1 和 結論 2 可知,

$\begin {aligned} T(m) &< cm + \frac {4}{m}d + \frac {2}{m}k \int_{2}^{m}i \ln {i}di \\ &< cm + \frac {4}{m}d + \frac {2}{m}k(\frac {1}{2}m^{2} \ln {m} - \frac {m^{2}}{4}) \\ &= cm + \frac {4}{m}d + km \cdot \ln {m} - \frac {k}{2}m < km \ln {m} \end {aligned}$
因此, 當 $n = m$ 時, 也有 $T(m) \leq kn \ln {n}$
綜上所述, $T(n) \leq kn \ln {n}$ . 故 $T(n) = O(n \log {n})$
根據 引理 1, 結合上面得到結論, 我們得到 $T(n) = \Theta(n \log {n})$ . 因此, 快速排序法的平均時間複雜度為 $\Theta(n \log {n}$
$\blacksquare$

上面, 我們僅僅分析了快速排序的平均時間複雜度, 但是在序列幾乎逆序或者逆序的情況下, 使用快速排序法, 將導致某一段總為空. 因此, 最壞情況下的快速排序法時間複雜度達到了 $\Theta(n^{2})$ . 為了解決這個問題, 如果已經知道序列總體排列的情況下, 可以通過選取序列中間元素或者隨機選取元素作為支點來降低時間複雜度