快速排序（Quicksort）是對冒泡排序的一種改進。它的基本思想是：通過一趟排序將要排序的數據分割成獨立的兩部分，其中一部分的所有數據都比另外一部分的所有數據都要小，然后再按此方法對這兩部分數據分別進行快速排序，整個排序過程可以遞歸進行，以此達到整個數據變成有序序列。快速排序不穩定，O(log(n))的額外空間，時間復雜度為O(nlog(n))，不是自適應的。

快速排序(Quicksort)有幾個值得一提的變種算法，這里進行一些簡要介紹：

隨機化快排：快速排序的最壞情況基于每次劃分對主元的選擇。基本的快速排序選取第一個元素作為主元。這樣在數組已經有序的情況下，每次劃分將得到最壞的結果。一種比較常見的優化方法是隨機化算法，即隨機選取一個元素作為主元。這種情況下雖然最壞情況仍然是O(n^2)，但最壞情況不再依賴于輸入數據，而是由于隨機函數取值不佳。實際上，隨機化快速排序得到理論最壞情況的可能性僅為1/(2^n)。所以隨機化快速排序可以對于絕大多數輸入數據達到O(nlogn)的期望時間復雜度。一位前輩做出了一個精辟的總結：“隨機化快速排序可以滿足一個人一輩子的人品需求。”

隨機化快速排序的唯一缺點在于，一旦輸入數據中有很多的相同數據，隨機化的效果將直接減弱。對于極限情況，即對于n個相同的數排序，隨機化快速排序的時間復雜度將毫無疑問的降低到O(n^2)。解決方法是用一種方法進行掃描，使沒有交換的情況下主元保留在原位置。

平衡快排（Balanced Quicksort）：每次盡可能地選擇一個能夠代表中值的元素作為關鍵數據，然后遵循普通快排的原則進行比較、替換和遞歸。通常來說，選擇這個數據的方法是取開頭、結尾、中間3個數據，通過比較選出其中的中值。取這3個值的好處是在實際問題（例如信息學競賽……）中，出現近似順序數據或逆序數據的概率較大，此時中間數據必然成為中值，而也是事實上的近似中值。萬一遇到正好中間大兩邊小（或反之）的數據，取的值都接近最值，那么由于至少能將兩部分分開，實際效率也會有2倍左右的增加，而且利于將數據略微打亂，破壞退化的結構。

外部快排（External Quicksort）：與普通快排不同的是，關鍵數據是一段buffer，首先將之前和之后的M/2個元素讀入buffer并對該buffer中的這些元素進行排序，然后從被排序數組的開頭（或者結尾）讀入下一個元素，假如這個元素小于buffer中最小的元素，把它寫到最開頭的空位上；假如這個元素大于buffer中最大的元素，則寫到最后的空位上；否則把buffer中最大或者最小的元素寫入數組，并把這個元素放在buffer里。保持最大值低于這些關鍵數據，最小值高于這些關鍵數據，從而避免對已經有序的中間的數據進行重排。完成后，數組的中間空位必然空出，把這個buffer寫入數組中間空位。然后遞歸地對外部更小的部分，循環地對其他部分進行排序。

三路基數快排（Three-way Radix Quicksort，也稱作Multikey Quicksort、Multi-key Quicksort）：結合了基數排序（radix sort，如一般的字符串比較排序就是基數排序）和快排的特點，是字符串排序中比較高效的算法。該算法被排序數組的元素具有一個特點，即multikey，如一個字符串，每個字母可以看作是一個key。算法每次在被排序數組中任意選擇一個元素作為關鍵數據，首先僅考慮這個元素的第一個key（字母），然后把其他元素通過key的比較分成小于、等于、大于關鍵數據的三個部分。然后遞歸地基于這一個key位置對“小于”和“大于”部分進行排序，基于下一個key對“等于”部分進行排序。

代碼實現：

public class QuickSort {   
public static void sort(Comparable[] data, int low, int high) {   
// 樞紐元,一般以第一個元素為基準進行劃分   
int i = low;   
int j = high;   
if (low < high) {   
// 從數組兩端交替地向中間掃描   
Comparable pivotKey = data[low];   
// 進行掃描的指針i,j;i從左邊開始,j從右邊開始   
while (i < j) {   
while (i < j && data[j].compareTo(pivotKey) > 0) {   
j--;   
}// end while   
if (i < j) {   
// 比樞紐元素小的移動到左邊   
data[i] = data[j];   
i++;   
}// end if   
while (i < j && data[i].compareTo(pivotKey) < 0) {   
i++;   
}// end while   
if (i < j) {   
// 比樞紐元素大的移動到右邊   
data[j] = data[i];   
j--;   
}// end if   
}// end while   
// 樞紐元素移動到正確位置   
data[i] = pivotKey;   
// 前半個子表遞歸排序   
sort(data, low, i - 1);   
// 后半個子表遞歸排序   
sort(data, i + 1, high);   
}// end if   
}// end sort   
public static void main(String[] args) {   
// 在JDK1.5版本以上,基本數據類型可以自動裝箱   
// int,double等基本類型的包裝類已實現了Comparable接口   
Comparable[] c = { 4, 9, 23, 1, 45, 27, 5, 2 };   
sort(c, 0, c.length - 1);   
for (Comparable data : c) {   
System.out.println(data);   
}   
}   
} 

快速排序是目前使用的最廣泛的排序算法了，快速排序的核心在于分割算法，也可以說是最有技巧的部分。希望通過本文的介紹，能給你帶來幫助。

【編輯推薦】

1. 5.11 三行代碼的快速排序
2. 12.3.2 基于任務竊取的快速排序
3. 19.4.2 用Parallel_For進行并行快速排序
4. C#快速排序的趣味實現：從Haskell說起