quicksort可以說是應用最廣泛的排序算法之一，它的基本思想是分治法，選擇一個pivot(中軸點），将小于pivot放在左邊，将大于 pivot放在右邊，針對左右兩個子序列重複此過程，直到序列為空或者隻有一個元素。這篇blog主要目的是關注quicksort可能的改進方法，并對 這些改進方法做評測。其目的是為了了解arrays.sort(int [ ]a)的實作。實作本身有paper介紹。
quicksort一個教科書式的簡單實作，采用左端點做pivot(《算法導論》上僞代碼是以右端點做pivot)：
[java]
public void qsort1(int[] a, int p, int r) {
// 0個或1個元素，傳回
if (p >= r)
return;
// 選擇左端點為pivot
int x = a[p];
int j = p;
for (int i = p + 1; i <= r; i++) {
// 小于pivot的放到左邊
if (a[i] < x) {
swap(a, ++j, i);
}
// 交換左端點和pivot位置
swap(a, p, j);
// 遞歸子序列
qsort1(a, p, j - 1);
qsort1(a, j + 1, r);
[/java]
quicksort的最佳情況下的時間複雜度o(n logn)，最壞情況下的時間複雜度是o(n^2)，退化到插入排序的最壞情況，平均情況下的平均複雜度接近于最佳情況也就是o(nlog n)，這也是基于比較的排序算法的比較次數下限。
為了對排序算法的性能改進有個直覺的對比，我們建立一個測試基準，分别測試随機數組的排序、升序數組的排序、降序數組的排序以及重複元素的數組排序。首先 使用java.util.arrays.sort建立一個評測基準，注意這裡的時間機關是秒，這些絕對時間沒有意義，我們關注的是相對值，是以這裡我不會 列出詳細的評測程式：
算法
随機數組
升序數組
降序數組
重複數組
arrays.sort
136.293
0.548
0.524
26.822
qsort1對于輸入做了假設，假設輸入是随機的數組，如果排序已經排序的數組，qsort1馬上退化到o(n^2)的複雜度，這是由于標明的pivot每次都會跟剩餘的所有元素做比較。它跟arrays.sort的比較：
qsort1
134.475
48.498
141.968
45.244
果然，在排序已經排序的數組的時候，qsort的性能跟arrays.sort的差距太大了。那麼我們能做的第一個優化是什麼？答案是将pivot的選擇随機化，不再是固定選擇左端點，而是利用随機數産生器選擇一個有效的位置作為pivot，這就是qsort2:
public void qsort2(int[] a, int p, int r) {
// 随機選擇pivot
int i = p + rand.nextint(r - p + 1);
// 交換pivot和左端點
swap(a, p, i);
// 劃分算法不變
for (i = p + 1; i <= r; i++) {
qsort2(a, p, j - 1);
qsort2(a, j + 1, r);
再次進行測試，檢視qsort1和qsort2的對比：
qsort2
227.87
19.009
18.597
74.639
從随機數組的排序來看，qsort2比之qsort1還有所下降，這主要是随機數産生器帶來的消耗，但是在已經排序數組的排序上面，qsort2有很大進步，在有大量随機重複元素的數組排序上，qsort2卻有所下降，主要消耗也是來自随機數産生器的影響。
更進一步的優化是在劃分算法上，現在的劃分算法隻使用了一個索引i，i從左向右掃描，遇到比pivot小的，就跟從p+1開始的位置（由j索引進行遞增标 志）進行交換，最終的劃分點落在了j，然後将pivot調換到j上，再遞歸排序左右兩邊子序列。一個更高效的劃分過程是使用兩個索引i和j，分别從左右兩 端進行掃描，i掃描到大于等于pivot的元素就停止，j掃描到小于等于pivot的元素也停止，交換兩個元素，持續這個過程直到兩個索引相遇，此時的 pivot的位置就落在了j，然後交換pivot和j的位置，後續的工作沒有不同,示意圖
改進後的qsort3代碼如下：
public void qsort3(int[] a, int p, int r) {
這裡要用do……while是因為i索引的初始位置是pivot值存儲的左端點，而j所在初始位置是右端點之外，是以都需要先移動一個位置才是合法的。檢視下qsort2和qsort3的基準測試對比：
qsort3
229.44
18.696
18.507
43.428
可以看到qsort3的改進主要展現在了大量重複元素的數組的排序上，這是因為qsort3在遇到跟pivot相等的元素的時候，還是進行停止并交換，而 非跳過；假設遇到相等的元素你不停止，那麼這些相等的元素在下次劃分的時候需要再次進行比較，比較次數退化到最差情況的o(n^2)，而通過在遇到相等元 素的時候停止并交換，盡管增加了交換的次數，但是卻避免了所有元素相同情況下最差情況的發生。
改進到這裡，回頭看看我們做了什麼，首先是使用随機挑選pivot替代固定選擇，其次是改進了劃分算法，從兩端進行掃描替代單向查找，并仔細處理元素相同的情況。
插入排序的時間複雜度是o(n^2)，但是在已經排序好的數組上面，插入排序的最佳情況是o(n)，插入排序在小數組的排序上是非常高效的，這給我們一個 提示，在快速排序遞歸的子序列，如果序列規模足夠小，可以使用插入排序替代快速排序，是以可以在快排之前判斷數組大小，如果小于一個閥值就使用插入排序， 這就是qsort4:
public void qsort4(int[] a, int p, int r) {
如果數組大小小于7就使用插入排序，7這個數字完全是經驗值。檢視qsort3和qsort4的測試比較：
qsort4
173.201
7.436
7.477
32.195
qsort4改進的效果非常明顯，所有基準測試的結果都取得了明顯的進步。qsort4還有一種變形，現在是在每個遞歸的子序列上進行插入排序，也可以換一種形式，當小于某個特定閥值的時候直接傳回不進行任何排序，在遞歸傳回之後，對整個數組進行一次插入排序，這個時候整個數組是由一個一個沒有排序的子序列按照順序組成的，是以插入排序可以很快地将整個數組排序，這個變形的qsort5跟qsort4沒有本質上的不同：
public void qsort5(int[] a, int p, int r) {
基準測試的結果也證明了qsort4和qsort5是一樣的：
qsort5
175.031
7.324
7.453
32.322
現在，最大的開銷還是随機數産生器選擇pivot帶來的開銷，我們用随機數産生器來選擇pivot，是希望pivot能盡量将數組劃分得均勻一些，可以選 擇一個替代方案來替代随機數産生器來選擇pivot，比如三數取中，通過對序列的first、middle和last做比較，選擇三個數的中間大小的那一 個做pivot，從機率上可以将比較次數下降到12/7 ln(n)。
median-of-three對小數組來說有很大的機率選擇到一個比較好的pivot，但是對于大數組來說就不足以保證能夠選擇出一個好的pivot， 是以還有個辦法是所謂median-of-nine，這個怎麼做呢？它是先從數組中分三次取樣，每次取三個數，三個樣品各取出中數，然後從這三個中數當中 再取出一個中數作為pivot，也就是median-of-medians。取樣也不是亂來，分别是在左端點、中點和右端點取樣。什麼時候采用 median-of-nine去選擇pivot，這裡也有個數組大小的閥值，這個值也完全是經驗值，設定在40，大小大于40的數組使用median-of-nine選擇pivot，大小在7到40之間的數組使用three-of-median選擇pivot,大小等于7的數組直接選擇中數作為pivot，大小小于7的數組則直接使用插入排序，這就是改進後的qsort6，已經非常接近于arrays.sort的實作：
public void qsort6(int[] a, int p, int r) {
其中的med3函數用于取三個數的中數：
private static int med3(int x[], int a, int b, int c) {
return x[a] < x[b] ? (x[b] < x[c] ? b : x[a] < x[c] ? c : a)
: x[b] > x[c] ? b : x[a] > x[c] ? c : a;
運作基準測試跟qsort4進行比較：
qsort6
143.264
0.54
0.836
27.311
觀察到qsort6的改進也非常明顯，消除了随機産生器帶來的開銷，取中數的時間複雜度在o(1)。此時qsort6跟arrays.sort的差距已經 非常小了。array.sort所做的最後一個改進是針對劃分算法，采用了所謂”split-end”的劃分算法，這主要是為了針對equals的元素， 降低equals元素參與遞歸的開銷。我們原來的劃分算法是分為兩個區域加上一個pivot：
跟pivot equals的元素分散在左右兩個子序列裡，繼續參與遞歸調用。當數組裡的相同元素很多的時候，這個開銷是不可忽視的，是以一個方案是将這些相同的元素集 中存放到中間這個地方，不參與後續的遞歸處理，這就是”fat partition”，此時是将數組劃分為3個區域：小于pivot，等于pivot以及大于pivot:
但是arrays.sort采用的卻不是”fat partition”，這是因為fat partition的實作比較複雜并且低效，arrays.sort是将與pivot相同的元素劃分到兩端，也就是将數組分為了4個區域：
這就是split-end名稱的由來，這個算法的實作可以跟qsort3的改進結合起來，同樣是進行兩端掃描，但是遇到equals的元素不是進行互換， 而是各自交換到兩端。當掃描結束，還要将兩端這些跟pivot equals的元素交換到中間位置，不相同的元素交換到兩端，左邊仍然是比pivot小的，右邊是比pivot大的，分别進行遞歸的快速排序處理，這樣改 進後的算法我們成為qsort7:
public void qsort7(int[] x, int p, int r) {
其中用到了vecswap方法用于批量交換一批資料，将a位置（包括a)之後n個元素與b位置(包括b)之後n個元素進行交換：
private static void vecswap(int x[], int a, int b, int n) {
for (int i = 0; i < n; i++, a++, b++)
swap(x, a, b);
主要是用于劃分後将兩端與pivot相同的元素交換到中間來。qsort7的實作跟arrays.sort的實作是一樣的，看看split-end劃分帶來的改進跟qsort6的對比：
140.468
0.491
0.506
26.639
這個結果跟arrays.sort保持一緻。
最後給幾張7個快排程式的在4種測試中的對比圖
還可以做的優化：
1、内聯swap和vecswap函數，循環中的swap調用可以展開。
2、改進插入排序，這是《程式設計珠玑》裡提到的，減少取值次數。
for (int i = p; i <= r; i++) {
int t = x[i];
int j = i;
for (; j > p && x[j - 1] > t; j–) {
x[j] = x[j - 1];
x[j] = t;
3、遞歸可以展開為循環，最後一個遞歸調用是尾遞歸調用，很容易展開為循環，左子序列的遞歸調用就沒那麼容易展開了。
4、嘗試更多取樣算法來提高選擇好的pivot的機率。
5、遞歸處理并行化
本文來源于"阿裡中間件團隊播客",原文時間"2010-09-08"