標籤：

快速排序(Quick Sort)詳解

02-10
演算法研究是計算機科學中重要的一個分支。眾多基礎演算法中，比較排序演算法是基礎中的基礎。本文主要介紹一種經典的比較排序演算法----快速排序演算法（由Tony Hoare於1961年發表）的基本思路，優點以及時間和空間複雜度分析。

比較排序演算法

簡單而言，比較排序演算法是對兩個元素進行比較來決定兩個元素的在輸出序列中相對位置（誰在前面誰在後面）的排序演算法。從數學意義說，比較排序演算法要求序列中的元素滿足如下兩條性質：

a leq b and b leq c Rightarrow a leq c

forall a and b, a leq b is true or b leq a is true

比較排序演算法類似用天平來比較兩個物體之間誰的質量大小來排序

圖片來自互聯網：

upload-images.jianshu.io

時間複雜度下界

首先拋出結論，比較排序演算法的下界是Theta(ncdot log_2n)。證明方法有很多，演算法導論中用的是決策樹模型證明（The decision-tree model）。我在這裡想展示另外一種證明方法：信息熵（因為我是通信狗出身，雖然現在已經拜在圖靈的門下，但香農仍是我的祖師爺啊）。熵值的數學表達為

H(X)=-sum_{i}{}P(X_i)cdot log_2(P(X_i))

如果序列長度為n，那麼對序列排序後則可能有 n! 種結果。如果輸入序列是完全隨機序列，則每種結果的概率是相等的。具體到比較排序演算法和之前的熵值公式

iin[1,n!],forall iin[1,n!], P(X_i) = frac{1}{n!}

帶回熵值公式

H(X) = -n!cdot frac{1}{n!}log_2{(frac{1}{n!})}=log_2{(n!)}

演算法導論中3.19證明了

log_2{(n!)}=Theta(ncdot log_2(n))

也就是說，針對排序而言，一個長度為n的序列，其蘊含的信息量為

Theta(ncdot log_2(n))

接下來我們分析一下一次比較操作所消除的信息量。對於任意的a和b，假設 p 為 a < b 的概率，那麼一次比較操作所能消除的信息量C為

-pcdot log_2{(p)}-(1-p)cdot log_2{(1-p)}

對於隨機序列，p = 0.5,C=1，這也是C能取到的最大值。所以想用比較操作來完成序列排序，至少要

frac{Theta(ncdot log_2(n))}{1}=Theta(ncdot log_2(n))次比較操作。

常見的比較排序演算法

  1. 冒泡排序（Bubble Sort）時間複雜度和空間複雜度為Theta(n^2), Theta(n)。

  2. 插入排序（Insertion Sort） 時間複雜度下界，上界以及空間複雜度為Omega(n), O(n^2) and Theta(n)。

  3. 歸併排序（Merge Sort）時間複雜度和空間複雜度為Theta(n cdot log_2(n)) and Theta(n cdot log_2(n))。可見雖然歸併排序的時間複雜度符合理論最小值，但它的空間複雜度也很高。更蛋疼的是歸併排序的時間複雜度分析是建立在RAM模型（Random Access Memory）上，而實際的計算機內存模型並不是RAM而是有cache的。因為歸併排序演算法在每次遞歸迭代過程中都會申請新的內存然後在新申請內存上進行操作。這不匹配於cache內存機制，所以歸併排序演算法在真實硬體上的表現不很理想。不過隨著並行，分散式系統的興起，這個演算法又有了新的生機。它非常適合併行優化，並且已經有了相應分析和研究（如果這篇反響好我第二篇就寫這個內容）。

快速排序演算法

快速排序則充分利用了cache機制，演算法的偽碼是

algorithm quicksort(A, lo, hi) if lo < hi then p := partition(A, lo, hi) quicksort(A, lo, p – 1) quicksort(A, p + 1, hi)

algorithm partition(A, lo, hi) pivot := A[hi] i := lo for j := lo to hi – 1 do if A[j] ≤ pivot then swap A[i] with A[j] i := i + 1 swap A[i] with A[hi] return i

顯然，快速排序的時間複雜度的下界，上界以及空間複雜度為Omega(n cdot log_2(n)), O(n^2) and Theta(n).

看上去並不怎麼樣。但因為輸入序列為隨機序列，所以我們還得關注下時間複雜度的期望值。

在演算法導論中，快速排序的時間複雜度期望值證明思路如下

  • 猜測其時間複雜度的期望值為Theta(n cdot log_2(n))

  • 再用數學歸納法證明

但作為強迫症晚期的我總覺得這個方法不夠酷炫，因為猜測時間複雜度期望值這一步總有一種碰運氣的感覺（當然這是調侃的說法，其實這種思路在數學證明中有時候很有用）。基於此，向大家隆重推出下面這種方法，簡直是狂拽酷炫屌炸天（純個人主觀喜好。。。。）。假設E(n)為輸入序列長度為n時期望的時間複雜度，則

E(n)=frac{1}{n}(E(0)+E(n-1))+frac{1}{n}(E(1)+E(n-2))+...+frac{1}{n}(E(n-1)+E(0))+n+1=frac{2}{n}sum_{i=0}^{n-1}E(i)+n+1 Rightarrow

n cdot E(n)=2cdot sum_{i=0}^{n-1}E(i)+(n+1)cdot n

那麼

(n-1) cdot E(n-1)=2cdot sum_{i=0}^{n-2}E(i)+ncdot (n-1)

兩式相減

n cdot E(n)-(n-1) cdot E(n-1)=2cdot E(n-1)+2 cdot n Rightarrow

n cdot E(n)=(n+1) cdot E(n-1)+2 cdot n

我們將這個等式一般化

a_n cdot E(n)=b_n cdot E(n-1)+c_n

a_n=n,b_n=n+1,c_n=2cdot n

接下來我們將一般化後的等式兩邊變形為

s_n cdot a_ncdot E(n)=s_n cdot b_ncdot E(n-1)+s_n cdot c_n

我們假設這個參數選擇得非常好，巧妙的滿足

S_n=s_ncdot a_n and S_{n-1}=s_ncdot b_n

所以等式可以變形為

S_ncdot E(n)=S_{n-1}cdot E(n-1)+s_ncdot c_n

化簡

S_ncdot E(n)=S_0cdot E(0)+sum_{i=0}^{n}s_icdot c_i

S_n=s_ncdot a_n, S_{n-1}=s_ncdot b_nRightarrow S_{n-1}=s_ncdot b_n=s_{n-1}cdot a_{n-1}Rightarrow

s_n=frac{s_{n-1}cdot a_{n-1}}{b_n}

迭代則有

s_n=frac{a_{n-1}cdot a_{n-2}cdot ...cdot a_{1}}{b_ncdot b_{n-1}cdot ...cdot b_{2}}

我們將

a_n=n,b_n=n+1,c_n=2cdot n代入後得到

s_n=frac{2}{(n+1)cdot n}

frac{2}{n+1}cdot E(n)=S_0cdot E(0)+sum_{i=1}^{n}frac{4}{i}

因為E(0)=0

E(n)=2cdot (n+1)cdotsum_{i=1}^{n}frac{1}{i}

從演算法導論的A.7可知

sum_{i=1}^{n}frac{1}{i}=log_2(n)+O(1)

所以

E(n)=Theta(ncdot log_2(n))

上述證明來自於具體數學（concrete mathematics）第二章

總結

時間複雜度的期望值符合理論最小值，並且空間複雜度只有O(n)，能夠很好的利用cache機制。所以快速排序是很不錯的串列比較排序演算法，特別是在真實的硬體上，所以gcc中還有qsort這個庫函數（stdlib.h）。

之所以介紹這個證明辦法是因為演算法導論中的證明方法證明了快速排序的期望運行時間是Theta(ncdot log_2(n))，而具體數學中的方法不僅證明了這個結論，還算出了常量 c=2，太帥了。

推薦閱讀：

※演算法競賽和數學競賽對選手的考察點有什麼不同?
※如何設計分銷系統中 多級用戶關係的 數據結構?
※九層循環怎麼寫
※遞歸演算法的時間複雜度？
※成功人士從不刷Leetcode（2）

TAG:算法 |