快速排序（英文名：Quicksort，有時候也叫做劃分交換排序）是一個高效的排序算法，由Tony Hoare在1959年發明（1961年公布）。當情況良好時，它可以比主要競争對手的歸并排序和堆排序快上大約兩三倍。這是一個分治算法，而且它就在原地排序。
所謂原地排序，就是指在原來的資料區域内進行重排，就像插入排序一般。而歸并排序就不一樣，它需要額外的空間來進行歸并排序操作。為了線上性時間與空間内歸并，它不能線上性時間内實作就地排序，原地排序對它來說并不足夠。而快速排序的優點就在于它是原地的，也就是說，它很節省記憶體。
引用一張來自維基百科的能夠非常清晰表示快速排序的示意圖如下：
由于快速排序采用了分治算法，是以：
一、分解：本質上快速排序把資料劃分成幾份，是以快速排序通過選取一個關鍵資料，再根據它的大小，把原數組分成兩個子數組：第一個數組裡的數都比這個主中繼資料小或等于，而另一個數組裡的數都比這個主中繼資料要大或等于。
二、解決：用遞歸來處理兩個子數組的排序。 （也就是說，遞歸地求上面圖示中左半部分，以及遞歸地求上面圖示中右半部分。）
三、合并：因為子數組都是原址排序，是以不需要合并操作，通過上面兩步後數組已經排好序了。
是以快速排序的主要思想是遞歸與劃分。
當然最重要的是它的複雜度是線性的，也就是Θ(n)個劃分的子程式。
1
2
3
4
5
6
7
8
9
這就是劃分的僞代碼，基本的結構就是一個for循環語句，中間加上了一個if條件語句，它實作了對子數組A[p...q]的原址排序。
剛開始時i等于p，j等于p+1。在這個循環中查找i下标的資料，如果它比x大，那就将其存放到“>=x”區域并将j加1後進行下一次循環。而如果它比x小，那就要做些動作來維持循環不變量了。将i的下标加1後将下标i對應的資料和下标j所對應的資料互換位置。然後再移動區域的界限并開始下一次循環。
那麼這個算法在n個資料下的運作時間大約是O(n)，因為它幾乎把每個數都比較了一遍，而每個步驟所需的時間都為O(1)。
上面這幅圖詳細的描述了Partition過程，每一行後也加了注釋。
有了上面這些準備工作，再加上分治的思想實作快速排序的僞代碼也是很簡單的。
為了排序一個數組A的全部元素，初始調用時Quicksort(A,1,A.length)。
相信通過前面的諸多實踐，大家也發現了快速排序的運作時間依賴于Partition過程，也就是依賴于劃分是否平衡，而歸根結底這還是由于輸入的元素決定的。
如果劃分是平衡的，那麼快速排序算法性能就和歸并排序一樣。
如果劃分是不平衡的，那麼快速排序的性能就接近于插入排序。
1）輸入的元素已經排序或逆向排序
2）每個劃分的一邊都沒有元素
也就是說當劃分産生的兩個子問題分别包含了n-1個元素和0個元素時，快速排序的最壞情況就發生了。
T(n)=T(0)+T(n−1)+\Theta(n)=Θ(1)+T(n−1)+Θ(n)=Θ(n−1)+Θ(n)=Θ(n2)
這是一個等差級數，就和插入排序一樣。它并不比插入排序快，因為當同樣是輸入元素已經逆向排好序時，插入算法的運作時間為Θ(n)。但快速排序仍舊是一個優秀的算法，這是因為在平均情況下它已經很高效。
我們為最壞情況畫一個遞歸樹。
這是一課高度不平衡的遞歸樹，圖中左邊的那些T(0)的運作時間都為Θ(1)，而總共有n個。
是以算法的中運作時間為：
T(n)=Θ(n)+Θ(n2)=Θ(n2)
通過上面的圖示我們知道了在最壞情況下快速排序的複雜度是Θ(n2)，但以圖示的方式并不是一種嚴謹的證明方式，我們應該使用代入法來證明它。
當輸入規模為n時，時間T(n)有如下遞歸式：
T(n)=max0≤r≤n−1(T(r)+T(n−r−1))+Θ(n)
除去主元後，在Partition函數中生成的兩個子問題的規模的和為n-1，是以r的規模才是0到n-1。
假設T(n)≤cn2成立，其中c為常數這個大家都知道的。于是上面的遞歸式為：
T(n)≤max0≤r≤n−1(cr2+c(n−r−1)2)+Θ(n)≤c∗max0≤r≤n−1(r2+(n−r−1)2)+Θ(n)
1）而r2+(n−r−1)2對于r的二階導數為正，是以在區間0≤r≤n−1的右端點取得最大值。
于是有max0≤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的二階導數為正，是以在區間0≤r≤n−1的左端點取得最小值。
于是有max0≤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将數組分為n/2和n/2兩個部分時是最高效的。此時有：
T(n)=2T(n/2)+Θ(n)=Θ(nlgn)
快速排序的平均運作時間更接近于其最好情況，而非最壞情況。
此處有一個經典的示例，将數組按1：9的比例進行劃分會怎樣呢？這種劃分看似很不平衡，但真的會是以而影響效率麼？
其中此時的遞歸式是：
T(n)=T(110n)+T(910n)+Θ(n)
這裡依舊通過遞歸樹來觀察一番。
因為每次都減少十分之一，需要減多少次才能達到n呢，也恰好也是以10為底對數的定義。是以左側的高度為log10n了，相應的右側的高度為log109n。
所有那些葉子加在一起也隻有Θ(n)，是以有：
T(n)≤cn∗log109n+Θ(n)
其實T(n)的下界也漸近為nlgn，是以總時間為：
T(n)=Θ(nlgn)
隻要劃分是常數比例的，算法的運作時間總是O(nlgn)。
在前面分析快速排序的平均情況性能時，是建立在輸入資料的所有排列都是等機率的條件下的，但在實際工程中往往不會總出現這種良好的情況。
以下是随機化快速排序的好處：
1）其運作時間不依賴與輸入序列的順序
2）無需對輸入序列的分布做任何假設
3）沒有 一種特别的輸入會引起最差的運作情況
4）最差的情況由随機數産生器決定
現在我們來使用一種叫做随機抽樣（random sampling）的随機化技術，使用該技術就不再始終采用A[p]作為主元，而是從A[p…q]中随機選擇一個元素作為主元。
為了達到這一目的，首先将A[p]與從A[p...q]中随機選出的一個元素交換。
通過對序列p...q的随機抽樣，我們可以保證主元元素x=A[p]是等機率地從子數組的q−p+1個元素中選取的。
因為主元元素是随機選擇的，我們可以期望在平均情況下對輸入數組的劃分是比較均衡的。是以對前面的兩份僞代碼做如下修改：
有了随機抽樣技術後再也不用擔心快速排序遇到最壞劃分的情況啦，是以說随機化快速排序的期望運作時間是O(nlgn)。
感謝您的通路，希望對您有所幫助。 歡迎大家關注、收藏以及評論。
為使本文得到斧正和提問，轉載請注明出處：
<a href="http://blog.csdn.net/nomasp">http://blog.csdn.net/nomasp</a>