算法介紹
快排圖 設要排序的數組是A[0]……A[N-1]，首先任意選取一個數據（通常選用數組的第一個數）作為關鍵數據，然後將所有比它小的數都放到它前面，所有比它大的數都放到它後面，這個過程稱為一趟快速排序。值得注意的是，快速排序不是一種穩定的排序算法，也就是說，多個相同的值的相對位置也許會在算法結束時產生變動。
一趟快速排序的算法是：
1）設定兩個變數i、j，排序開始的時候：i=0，j=N-1；
2）以第一個數組元素作為關鍵數據，賦值給 key，即 key=A[0]；
3）從j開始向前搜尋，即由後開始向前搜尋(j--)，找到第一個小於 key的值A[j]，將A[j]和A[i]互換；
4）從i開始向後搜尋，即由前開始向後搜尋(i++)，找到第一個大於 key的A[i]，將A[i]和A[j]互換；
5）重複第3、4步，直到i=j； (3,4步中，沒找到符合條件的值，即3中A[j]不小於 key,4中A[i]不大於 key的時候改變j、i的值，使得j=j-1，i=i+1，直至找到為止。找到符合條件的值，進行交換的時候i， j指針位置不變。另外，i==j這一過程一定正好是i+或j-完成的時候，此時令循環結束）。
排序演示
示例
假設用戶輸入了如下數組：
| 下標 | 0 | 1 | 2 | 3 | 4 | 5 |
| 數據 | 6 | 2 | 7 | 3 | 8 | 9 |
創建變數i=0（指向第一個數據）, j=5(指向最後一個數據), k=6(賦值為第一個數據的值)。
我們要把所有比k小的數移動到k的左面，所以我們可以開始尋找比6小的數，從j開始，從右往左找，不斷遞減變數j的值，我們找到第一個下標3的數據比6小，於是把數據3移到下標0的位置，把下標0的數據6移到下標3，完成第一次比較：
| 下標 | 0 | 1 | 2 | 3 | 4 | 5 |
| 數據 | 3 | 2 | 7 | 6 | 8 | 9 |
i=0 j=3 k=6
接著，開始第二次比較，這次要變成找比k大的了，而且要從前往後找了。遞加變數i，發現下標2的數據是第一個比k大的，於是用下標2的數據7和j指向的下標3的數據的6做交換，數據狀態變成下表：
| 下標 | 0 | 1 | 2 | 3 | 4 | 5 |
| 數據 | 3 | 2 | 6 | 7 | 8 | 9 |
i=2 j=3 k=6
稱上面兩次比較為一個循環。
接著，再遞減變數j，不斷重複進行上面的循環比較。
在本例中，我們進行一次循環，就發現i和j“碰頭”了：他們都指向了下標2。於是，第一遍比較結束。得到結果如下，凡是k(=6)左邊的數都比它小，凡是k右邊的數都比它大：
| 下標 | 0 | 1 | 2 | 3 | 4 | 5 |
| 數據 | 3 | 2 | 6 | 7 | 8 | 9 |
如果i和j沒有碰頭的話，就遞加i找大的，還沒有，就再遞減j找小的，如此反覆，不斷循環。注意判斷和尋找是同時進行的。
然後，對k兩邊的數據，再分組分別進行上述的過程，直到不能再分組為止。
注意：第一遍快速排序不會直接得到最終結果，只會把比k大和比k小的數分到k的兩邊。為了得到最後結果，需要再次對下標2兩邊的數組分別執行此步驟，然後再分解數組，直到數組不能再分解為止（只有一個數據），才能得到正確結果。
調用函式
在c++中可以用函式qsort（）可以直接為數組進行排序。
用 法:
void qsort(void *base, int nelem, int width, int (*fcmp)(const void *,const void *));
參數：
1 待排序數組首地址
2 數組中待排序元素數量
3 各元素的占用空間大小
4 指向函式的指針，用於確定排序的順序
示例代碼
GO
Ruby
Erlang語言
Haskell語言
C++語言
C語言版本
JavaScript
Java
C#
運行結果：27 38 13 49 76 97 65
13 27 38 49 76 97 65
13 27 38 49 65 76 97
快速排序就是遞歸調用此過程——在以49為中點分割這個數據序列，分別對前面一部分和後面一部分進行類似的快速排序，從而完成全部數據序列的快速排序，最後把此數據序列變成一個有序的序列，根據這種思想對於上述數組A的快速排序的全過程如圖6所示：
初始狀態 {49 38 65 97 76 13 27} 進行一次快速排序之後劃分為 {27 38 13} 49 {76 97 65} 分別對前後兩部分進行快速排序{27 38 13} 經第三步和第四步交換後變成 {13 27 38} 完成排序。{76 97 65} 經第三步和第四步交換後變成 {65 76 97} 完成排序。圖示
F#
PHP
Pascal
Python3：分而治之+遞歸
最佳化
三平均分區法
關於這一改進的最簡單的描述大概是這樣的：與一般的快速排序方法不同，它並不是選擇待排數組的第一個數作為中軸，而是選用待排數組最左邊、最右邊和最中間的三個元素的中間值作為中軸。這一改進對於原來的快速排序算法來說，主要有兩點優勢：
（1） 首先，它使得最壞情況發生的幾率減小了。
（2） 其次，未改進的快速排序算法為了防止比較時數組越界，在最後要設定一個哨點。
根據分區大小調整算法
這一方面的改進是針對快速排序算法的弱點進行的。快速排序對於小規模的數據集性能不是很好。可能有人認為可以忽略這個缺點不計，因為大多數排序都只要考慮大規模的適應性就行了。但是快速排序算法使用了分治技術，最終來說大的數據集都要分為小的數據集來進行處理。由此可以得到的改進就是，當數據集較小時，不必繼續遞歸調用快速排序算法，而改為調用其他的對於小規模數據集處理能力較強的排序算法來完成。Introsort就是這樣的一種算法，它開始採用快速排序算法進行排序，當遞歸達到一定深度時就改為堆排序來處理。這樣就克服了快速排序在小規模數據集處理中複雜的中軸選擇，也確保了堆排序在最壞情況下O(n log n)的複雜度。
另一種最佳化改進是當分區的規模達到一定小時，便停止快速排序算法。也即快速排序算法的最終產物是一個“幾乎”排序完成的有序數列。數列中有部分元素並沒有排到最終的有序序列的位置上，但是這種元素並不多。可以對這種“幾乎”完成排序的數列使用插入排序算法進行排序以最終完成整個排序過程。因為插入排序對於這種“幾乎”完成的排序數列有著接近線性的複雜度。這一改進被證明比持續使用快速排序算法要有效的多。
另一種快速排序的改進策略是在遞歸排序子分區的時候，總是選擇優先排序那個最小的分區。這個選擇能夠更加有效的利用存儲空間從而從整體上加速算法的執行。
不同的分區方案考慮
對於快速排序算法來說，實際上大量的時間都消耗在了分區上面，因此一個好的分區實現是非常重要的。尤其是當要分區的所有的元素值都相等時，一般的快速排序算法就陷入了最壞的一種情況，也即反覆的交換相同的元素並返回最差的中軸值。無論是任何數據集，只要它們中包含了很多相同的元素的話，這都是一個嚴重的問題，因為許多“底層”的分區都會變得完全一樣。
對於這種情況的一種改進辦法就是將分區分為三塊而不是原來的兩塊：一塊是小於中軸值的所有元素，一塊是等於中軸值的所有元素，另一塊是大於中軸值的所有元素。另一種簡單的改進方法是，當分區完成後，如果發現最左和最右兩個元素值相等的話就避免遞歸調用而採用其他的排序算法來完成。
並行的快速排序
由於快速排序算法是採用分治技術來進行實現的，這就使得它很容易能夠在多台處理機上並行處理。
在大多數情況下，創建一個執行緒所需要的時間要遠遠大於兩個元素比較和交換的時間，因此，快速排序的並行算法不可能為每個分區都創建一個新的執行緒。一般來說，會在實現代碼中設定一個閥值，如果分區的元素數目多於該閥值的話，就創建一個新的執行緒來處理這個分區的排序，否則的話就進行遞歸調用來排序。
對於這一併行快速排序算法也有其改進。該算法的主要問題在於，分區的這一步驟總是要在子序列並行處理之前完成，這就限制了整個算法的並行程度。解決方法就是將分區這一步驟也並行處理。改進後的並行快速排序算法使用2n個指針來並行處理分區這一步驟，從而增加算法的並行程度。
變種
隨機化快排
快速排序的最壞情況基於每次劃分對主元的選擇。基本的快速排序選取第一個元素作為主元。這樣在數組已經有序的情況下，每次劃分將得到最壞的結果。一種比較常見的最佳化方法是隨機化算法，即隨機選取一個元素作為主元。這種情況下雖然最壞情況仍然是O(n^2)，但最壞情況不再依賴於輸入數據，而是由於隨機函式取值不佳。實際上，隨機化快速排序得到理論最壞情況的可能性僅為1/(2^n)。所以隨機化快速排序可以對於絕大多數輸入數據達到O(nlogn)的期望時間複雜度。一位前輩做出了一個精闢的總結：“隨機化快速排序可以滿足一個人一輩子的人品需求。”
隨機化快速排序的唯一缺點在於，一旦輸入數據中有很多的相同數據，隨機化的效果將直接減弱。對於極限情況，即對於n個相同的數排序，隨機化快速排序的時間複雜度將毫無疑問的降低到O(n^2)。解決方法是用一種方法進行掃描，使沒有交換的情況下主元保留在原位置。
平衡快排
每次儘可能地選擇一個能夠代表中值的元素作為關鍵數據，然後遵循普通快排的原則進行比較、替換和遞歸。通常來說，選擇這個數據的方法是取開頭、結尾、中間3個數據，通過比較選出其中的中值。取這3個值的好處是在實際問題中，出現近似順序數據或逆序數據的機率較大，此時中間數據必然成為中值，而也是事實上的近似中值。萬一遇到正好中間大兩邊小（或反之）的數據，取的值都接近最值，那么由於至少能將兩部分分開，實際效率也會有2倍左右的增加，而且利於將數據略微打亂，破壞退化的結構。
外部快排
與普通快排不同的是，關鍵數據是一段buffer，首先將之前和之後的M/2個元素讀入buffer並對該buffer中的這些元素進行排序，然後從被排序數組的開頭（或者結尾）讀入下一個元素，假如這個元素小於buffer中最小的元素，把它寫到最開頭的空位上；假如這個元素大於buffer中最大的元素，則寫到最後的空位上；否則把buffer中最大或者最小的元素寫入數組，並把這個元素放在buffer里。保持最大值低於這些關鍵數據，最小值高於這些關鍵數據，從而避免對已經有序的中間的數據進行重排。完成後，數組的中間空位必然空出，把這個buffer寫入數組中間空位。然後遞歸地對外部更小的部分，循環地對其他部分進行排序。
三路基數快排
（ Three-way Radix Quicksort，也稱作M ultikey Quicksort、Multi-key Quicksort）：結合了基數排序（radix sort，如一般的字元串比較排序就是基數排序）和快排的特點，是字元串排序中比較高效的算法。該算法被排序數組的元素具有一個特點，即multikey，如一個字元串，每個字母可以看作是一個key。算法每次在被排序數組中任意選擇一個元素作為關鍵數據，首先僅考慮這個元素的第一個key（字母），然後把其他元素通過key的比較分成小於、等於、大於關鍵數據的三個部分。然後遞歸地基於這一個key位置對“小於”和“大於”部分進行排序，基於下一個key對“等於”部分進行排序。
偽代碼
非隨機
QUICKSORT( A， p， r)
1 if p< r
2 then q ←PARTITION( A， p， r)
3 QUICKSORT( A， p， q-1)
4 QUICKSORT( A， q+1， r)
為排序一個完整的數組 A，最初的調用是QUICKSORT( A， 1， length[ A]）。
快速排序算法的關鍵是PARTITION過程，它對子數組A[p..r]進行就地重排：
PARTITION( A， p， r)
1 x← A[ r]
2 i← p-1
3 for j← p to r-1
4 do if A[ j]≤ x
5 then i← i+1
6 exchange A[ i]←→ A[ j]
7 exchange A[ i+1]←→ A[ r]
8 return i+1
隨機
對PARTITION和QUICKSORT所作的改動比較小。在新的劃分過程中，我們在真正進行劃分之前實現交換：
（其中PARTITION過程同 快速排序偽代碼（非隨機））
RANDOMIZED-PARTITION( A， p， r)
1 i← RANDOM( p， r)
2 exchange A[ r]←→ A[ i]
3 return PARTITION( A， p， r)
新的快速排序過程不再調用PARTITION，而是調用RANDOMIZED-PARTITION。
RANDOMIZED-QUICKSORT( A， p， r)
1 if p< r
2 then q← RANDOMIZED-PARTITION( A， p， r)
3 RANDOMIZED-QUICKSORT( A， p， q-1)
4 RANDOMIZED-QUICKSORT( A， q+1， r)
性能分析
這裡為方便起見，我們假設算法Quick_Sort的範圍閾值為1（即一直將線性表分解到只剩一個元素），這對該算法複雜性的分析沒有本質的影響。
我們先分析函式partition的性能，該函式對於確定的輸入複雜性是確定的。觀察該函式，我們發現，對於有n個元素的確定輸入L[p..r]，該函式運行時間顯然為θ（n）。
最壞情況
無論適用哪一種方法來選擇pivot，由於我們不知道各個元素間的相對大小關係（若知道就已經排好序了），所以我們無法確定pivot的選擇對劃分造成的影響。因此對各種pivot選擇法而言，最壞情況和最好情況都是相同的。
我們從直覺上可以判斷出最壞情況發生在每次劃分過程產生的兩個區間分別包含n-1個元素和1個元素的時候（設輸入的表有n個元素）。下面我們暫時認為該猜測正確，在後文我們再詳細證明該猜測。
對於有n個元素的表L[p..r]，由於函式Partition的計算時間為θ（n），所以快速排序在序壞情況下的複雜性有遞歸式如下：
T(1)=θ(1),T(n)=T(n-1)+T(1)+θ(n) (1)
用疊代法可以解出上式的解為T(n)=θ（n ）。
這個最壞情況運行時間與插入排序是一樣的。
下面我們來證明這種每次劃分過程產生的兩個區間分別包含n-1個元素和1個元素的情況就是最壞情況。
設T(n）是過程Quick_Sort作用於規模為n的輸入上的最壞情況的時間，則
T(n)=max(T(q)+T(n-q))+θ（n)，其中1≤q≤n-1 (2)
我們假設對於任何k
