什么是快速排序

快速排序簡介

快速排序（英文名：Quicksort，有時候也叫做劃分交換排序）是一個高效的排序算法，由Tony Hoare在1959年發(fā)明（1961年公布）。當情況良好時，它可以比主要競爭對手的歸并排序和堆排序快上大約兩三倍。這是一個分治算法，而且它就在原地排序。

所謂原地排序，就是指在原來的數(shù)據(jù)區(qū)域內(nèi)進行重排，就像插入排序一般。而歸并排序就不一樣，它需要額外的空間來進行歸并排序操作。為了在線性時間與空間內(nèi)歸并，它不能在線性時間內(nèi)實現(xiàn)就地排序，原地排序?qū)λ鼇碚f并不足夠。而快速排序的優(yōu)點就在于它是原地的，也就是說，它很節(jié)省內(nèi)存。

引用一張來自維基百科的能夠非常清晰表示快速排序的示意圖如下：

快速排序的分治思想

由于快速排序采用了分治算法，所以：

一、分解：本質(zhì)上快速排序把數(shù)據(jù)劃分成幾份，所以快速排序通過選取一個關(guān)鍵數(shù)據(jù)，再根據(jù)它的大小，把原數(shù)組分成兩個子數(shù)組：第一個數(shù)組里的數(shù)都比這個主元數(shù)據(jù)小或等于，而另一個數(shù)組里的數(shù)都比這個主元數(shù)據(jù)要大或等于。

二、解決：用遞歸來處理兩個子數(shù)組的排序。 （也就是說，遞歸地求上面圖示中左半部分，以及遞歸地求上面圖示中右半部分。）

三、合并：因為子數(shù)組都是原址排序，所以不需要合并操作，通過上面兩步后數(shù)組已經(jīng)排好序了。

所以快速排序的主要思想是遞歸與劃分。

如何劃分

當然最重要的是它的復(fù)雜度是線性的，也就是Θ(n)個劃分的子程序。

Partition(A,p,q)   // A[p,..q] 
1   x=A[p]   // pivot=A[p] 主元 
2   i=p 
3   for j=p+1 to q
4       do if A[j]<=x
5          then i=i+1 
6             exch A[i]<->A[j] 
7   exch A[p]<->A[i] 
8   return i // i pivot 
1
2
3
4
5
6
7
8
9

這就是劃分的偽代碼，基本的結(jié)構(gòu)就是一個for循環(huán)語句，中間加上了一個if條件語句，它實現(xiàn)了對子數(shù)組A[p...q]的原址排序。

剛開始時i等于p，j等于p+1。在這個循環(huán)中查找i下標的數(shù)據(jù)，如果它比x大，那就將其存放到“>=x”區(qū)域并將j加1后進行下一次循環(huán)。而如果它比x小，那就要做些動作來維持循環(huán)不變量了。將i的下標加1后將下標i對應(yīng)的數(shù)據(jù)和下標j所對應(yīng)的數(shù)據(jù)互換位置。然后再移動區(qū)域的界限并開始下一次循環(huán)。

那么這個算法在n個數(shù)據(jù)下的運行時間大約是O(n)，因為它幾乎把每個數(shù)都比較了一遍，而每個步驟所需的時間都為O(1)。

上面這幅圖詳細的描述了Partition過程，每一行后也加了注釋。

將遞歸的思想作用于劃分上

有了上面這些準備工作，再加上分治的思想實現(xiàn)快速排序的偽代碼也是很簡單的。

Quicksort(A,p,q) 
1   if p<q 
2     then r=Partition(A,p,q)   
3          Quicksort(A,p,r-1) 
4          Quicksort(A,r+1,q) 
1
2
3
4
5

為了排序一個數(shù)組A的全部元素，初始調(diào)用時Quicksort(A,1,A.length)。

快速排序的算法分析

相信通過前面的諸多實踐，大家也發(fā)現(xiàn)了快速排序的運行時間依賴于Partition過程，也就是依賴于劃分是否平衡，而歸根結(jié)底這還是由于輸入的元素決定的。

如果劃分是平衡的，那么快速排序算法性能就和歸并排序一樣。

如果劃分是不平衡的，那么快速排序的性能就接近于插入排序。

怎樣是最壞的劃分

1）輸入的元素已經(jīng)排序或逆向排序
2）每個劃分的一邊都沒有元素

也就是說當劃分產(chǎn)生的兩個子問題分別包含了n-1個元素和0個元素時，快速排序的最壞情況就發(fā)生了。

T(n)=T(0)+T(n?1)+\Theta(n)=Θ(1)+T(n?1)+Θ(n)=Θ(n?1)+Θ(n)=Θ(n2)

這是一個等差級數(shù)，就和插入排序一樣。它并不比插入排序快，因為當同樣是輸入元素已經(jīng)逆向排好序時，插入算法的運行時間為Θ(n)。但快速排序仍舊是一個優(yōu)秀的算法，這是因為在平均情況下它已經(jīng)很高效。

我們?yōu)樽顗那闆r畫一個遞歸樹。

這是一課高度不平衡的遞歸樹，圖中左邊的那些T(0)的運行時間都為Θ(1)，而總共有n個。

所以算法的中運行時間為：

T(n)=Θ(n)+Θ(n2)=Θ(n2)

最壞劃分的算法分析

通過上面的圖示我們知道了在最壞情況下快速排序的復(fù)雜度是Θ(n2)，但以圖示的方式并不是一種嚴謹?shù)淖C明方式，我們應(yīng)該使用代入法來證明它。

當輸入規(guī)模為n時，時間T(n)有如下遞歸式：

T(n)=max0≤r≤n?1(T(r)+T(n?r?1))+Θ(n)

除去主元后，在Partition函數(shù)中生成的兩個子問題的規(guī)模的和為n-1，所以r的規(guī)模才是0到n-1。

假設(shè)T(n)≤cn2成立，其中c為常數(shù)這個大家都知道的。于是上面的遞歸式為：

T(n)≤max0≤r≤n?1(cr2+c(n?r?1)2)+Θ(n)≤c?max0≤r≤n?1(r2+(n?r?1)2)+Θ(n)

1）而r2+(n?r?1)2對于r的二階導(dǎo)數(shù)為正，所以在區(qū)間0≤r≤n?1的右端點取得最大值。

于是有max0≤r≤n?1(r2+(n?r?1)2)≤(n?1)2=n2?2n+1，所以對于T(n)有：

T(n)≤cn2?c(2n?1)+Θ(n)

最終因為我們可以選擇一個足夠大的c，來使得c(2n?1)大于Θ(n)，所以有T(n)=O(n2)。

2）r2+(n?r?1)2對于r的二階導(dǎo)數(shù)為正，所以在區(qū)間0≤r≤n?1的左端點取得最小值。

于是有max0≤r≤n?1(r2+(n?r?1)2)≥(n?1)2=n2?2n+1，所以對于T(n)有：

T(n)≥cn2?c(2n?1)+Θ(n)

同樣我們也可以選擇一個足夠小的c，來使得c(2n?1)小于Θ(n)，所以有T(n)=Ω(n2)。

綜上這兩點得到T(n)=Θ(n2)

怎樣是最好的劃分

當Partition將數(shù)組分為n/2和n/2兩個部分時是最高效的。此時有：

T(n)=2T(n/2)+Θ(n)=Θ(nlgn)

怎樣是平衡的劃分

快速排序的平均運行時間更接近于其最好情況，而非最壞情況。

此處有一個經(jīng)典的示例，將數(shù)組按1：9的比例進行劃分會怎樣呢？這種劃分看似很不平衡，但真的會因此而影響效率么？

其中此時的遞歸式是：

T(n)=T(110n)+T(910n)+Θ(n)

這里依舊通過遞歸樹來觀察一番。

因為每次都減少十分之一，需要減多少次才能達到n呢，也恰好也是以10為底對數(shù)的定義。所以左側(cè)的高度為log10n了，相應(yīng)的右側(cè)的高度為log109n。

所有那些葉子加在一起也只有Θ(n)，所以有：

T(n)≤cn?log109n+Θ(n)

其實T(n)的下界也漸近為nlgn，所以總時間為：

T(n)=Θ(nlgn)

只要劃分是常數(shù)比例的，算法的運行時間總是O(nlgn)。

隨機化快速排序

隨機算法的思想

在前面分析快速排序的平均情況性能時，是建立在輸入數(shù)據(jù)的所有排列都是等概率的條件下的，但在實際工程中往往不會總出現(xiàn)這種良好的情況。

在【算法】3 由招聘問題看隨機算法中我們介紹了隨機算法，它使得對于所有的輸入都有著較好的期望性能，因此隨機化快速排序在有大量數(shù)據(jù)輸入的情況下是一種更好的排序算法。

以下是隨機化快速排序的好處：

1）其運行時間不依賴與輸入序列的順序

2）無需對輸入序列的分布做任何假設(shè)

3）沒有 一種特別的輸入會引起最差的運行情況

4）最差的情況由隨機數(shù)產(chǎn)生器決定

隨機抽樣技術(shù)

現(xiàn)在我們來使用一種叫做隨機抽樣（random sampling）的隨機化技術(shù)，使用該技術(shù)就不再始終采用A[p]作為主元，而是從A[p…q]中隨機選擇一個元素作為主元。

為了達到這一目的，首先將A[p]與從A[p...q]中隨機選出的一個元素交換。

通過對序列p...q的隨機抽樣，我們可以保證主元元素x=A[p]是等概率地從子數(shù)組的q?p+1個元素中選取的。

因為主元元素是隨機選擇的，我們可以期望在平均情況下對輸入數(shù)組的劃分是比較均衡的。所以對前面的兩份偽代碼做如下修改：

RANDOMIZED-PARTITION(A,p,q)
1   i=RANDOM(p,q)
2   exchange A[p] with A[i]
3   return PARTITION(A,p,q)
1
2
3
4

RANDOMIZED-QUICKSORT(A,p,q)
1   if p<q
2       r=RANDOMIZED-PARTITION(A,p,q)
3       RANDOMIZED-QUICKSORT(A,p,r-1)
4       RANDOMIZED-QUICKSORT(A,r+1,q)
1
2
3
4
5

有了隨機抽樣技術(shù)后再也不用擔心快速排序遇到最壞劃分的情況啦，所以說隨機化快速排序的期望運行時間是O(nlgn)。

感謝您的訪問，希望對您有所幫助。 歡迎大家關(guān)注、收藏以及評論。

為使本文得到斧正和提問，轉(zhuǎn)載請注明出處：
http://blog.csdn.net/nomasp