概述

快速排序是面試中的常見題，每次簡述一遍快速排序的原理便覺得仿佛已經(jīng)掌握了它揍诽。不是挺簡單的嗎诀蓉？然而實際實現(xiàn)的時候還是會遇到一些坑。于是寝姿，之前一次面試就跪了交排，很尷尬。所以饵筑，還是需要對它進行深入理解埃篓！

基本步驟

1. 檢查范圍，(以及終止條件)

注意遞歸終止條件

1. 選擇基準(pivot)根资，分割序列

即篩選不大于pivot的元素和不小于pivot的元素）架专，將pivot放至正確位置

2. 對pivot的左半段和右半段序列分別進行快速排序

參考[1], 我將快速排序的函數(shù)簽名定為
public <T extends Comparable<? super T>> void executeProcess(T[] sequ, int left, int right) { }

1.小數(shù)組優(yōu)化

遞歸的快速排序終會落入對于小數(shù)組的排序。而對于小數(shù)組的排序玄帕，快速排序不如插入排序部脚。

單位：nanosecond
環(huán)境：CPU 4核8線程 2.30GHZ

2.檢查范圍，以及終止條件

// 檢查下標是否越界
super.rangeCheck(sequ.length, left, right);

// 數(shù)組個數(shù)為0或1裤纹，已排序（終止條件）
int size = right - left + 1;
if (size < 2) {
    return;
}

3.選擇基準(pivot)委刘，分割序列

3.1 選擇基準

基準選擇常見的有以下三種方法丧没。

1. 序列首/序列尾
   對于有序序列分割極不平衡
2. 隨機選擇
   優(yōu)于序列首，但開銷不小
3. 三數(shù)中值分割
   它將考慮序列中left, right, (left + right) / 2這三個位置的元素值锡移，選擇它們的中位數(shù)作為基準

進一步呕童，可在三數(shù)中值分割的基礎(chǔ)上將三個位置上的較小值和較大值分別置于left位置、right位置淆珊。在使用下文的分割方式1時可保證兩個指針不越過序列端點夺饲。

// 三數(shù)排序決定基準，left/right/中位
int middle = (left + right) / 2;
if (sequ[left].compareTo(sequ[middle]) > 0) {
    swap(sequ, left, middle);
}
if (sequ[left].compareTo(sequ[right]) > 0) {
     swap(sequ, left, right);
}
if (sequ[middle].compareTo(sequ[right]) > 0) {
    swap(sequ, middle, right);
}
// 數(shù)組僅有2個或3個元素施符，此時已經(jīng)排好序
//（若對小數(shù)組使用插入排序往声，則該語句沒有必要）
if (!super.insertSortOptimized && middle == right - 1) {
    return super.InvalidPoint;
}
// 將基準（三數(shù)中值）放至right-1位置
swap(sequ, middle, right - 1);

3.2 分割策略

3.2.1 分割方式1

forePoint從前往后找大于pivot的元素，backPoint從后往前找小于pivot的元素戳吝，并交換浩销。
當forePoint與backPoint相遇后，將pivot放至正確位置骨坑。

分割方式1

之后以此類推
標紅的元素為pivot

// 對left+1和right-2之間的范圍進行分割
int forePoint = left;
int backPoint = right - 1;
T pivot = sequ[right - 1];

while (true) {
    while (sequ[++forePoint].compareTo(pivot) < 0) {
    }
    while (sequ[--backPoint].compareTo(pivot) > 0) {
    }

    if (forePoint >= backPoint) {
        // 將基準放到合適位置
        swap(sequ, forePoint, right - 1);
        break;
    } else {
        swap(sequ, forePoint, backPoint);
    }
}

相等元素的處理
當遇到和基準值相等的值時撼嗓，應(yīng)該如何處理？是往左半段移動欢唾？還是往右半段移動？
特別地粉捻，對于forePoint和backPoint同時分別遇到與基準值相等的元素時礁遣，應(yīng)該如何處理？
按照[1]中所說肩刃，forePoint和backPoint的地位應(yīng)是等價的祟霍，那么它們對于與基準值相等的元素的處理方式也應(yīng)相同。否則盈包，則會有左半段與右半段不均衡的情況出現(xiàn)沸呐，降低快速排序的效率。
那么我們還剩下forePoint和backPoint均停止(進行交換)和均不停止(不進行交換)的選擇呢燥。 [1]中推薦前種做法崭添。那么對于后種做法，可不可行呢叛氨？
針對上述的三種基準選擇方法分別進行分析：

• 前兩種選擇的基準均有可能是該序列中的最大值或者最小值呼渣，序列中可能存在其他與該值相同的元素，也可能不存在寞埠。因此屁置，必須考慮forePoint和backPoint越過序列端點的情況，停止與不停止并沒有差別仁连。
• 而對于三數(shù)中值分割蓝角，它所選擇的基準，最大僅可能是該序列中的次大值（可能等于最大值），或者最小僅可能是次小值（可能等于最小值）使鹅。若在三數(shù)中值分割的基礎(chǔ)上將三個位置上的較小值和較大值分別置于left位置揪阶、right位置，那么并徘，forePoint和backPoint則無法越過序列端點遣钳。但考慮到right位置與基準值相等的情況，若采用不停止的方式麦乞，則需要再次考慮forePoint越過序列端點的情況蕴茴，
  因此，遇到與基準相等的元素姐直，forePoint或者backPoint停止并且交換的做法相對更佳倦淀。

其實值等于pivot的元素在該次快速排序中，既可以隨便出現(xiàn)在左半段声畏，也可以隨便出現(xiàn)在右半段撞叽，不用恰好緊挨在該次被作為pivot的元素周圍。因為插龄，隨著之后對于左半段和右半段調(diào)用的快速排序愿棋，它們會各自被放到正確的位置上，這并不屬于該次快速排序的職責均牢。

3.2.2 分割方式2

curPoint從前往后遍歷序列糠雨，parPoint指向小于基準與大于等于基準的序列的分割位置 —— 大于等于基準的序列的第一個元素。
當curPoint遍歷結(jié)束徘跪，將pivot與parPoint位置的元素交換甘邀。

分割方式2

之后以此類推
標紅的元素為pivot

// 對left+1和right-2之間的范圍進行分割
int curPoint = left + 1;
int parPoint = left + 1;
T pivot = sequ[right - 1];

while(curPoint < right - 1) {
    if(sequ[curPoint].compareTo(pivot) < 0) {
        swap(sequ, curPoint, parPoint);
        parPoint++;
    }
    curPoint++;
}
swap(sequ, parPoint, right - 1);

4. 對pivot的左半段和右半段序列分別進行快速排序

4.1 遞歸

int partionPoint = partition(sequ, left, right);
if(partionPoint < 0) {
    return;
}
executeProcess(sequ, left, partionPoint - 1);
executeProcess(sequ, partionPoint + 1, right);

4.2 非遞歸

采用棧保存下次要進行分割的序列首尾位置，深度優(yōu)先垮庐。

Stack<Integer> stack = new Stack<Integer>();

int partionPoint = partition(sequ, left, right);
if(partionPoint < 0) {
    return;
}

stack.push(partionPoint + 1);
stack.push(right);

stack.push(left);
stack.push(partionPoint - 1);

while(!stack.isEmpty()) {
    int sRight = stack.pop();
    int sLeft = stack.pop();

    partionPoint = partition(sequ, sLeft, sRight);
    if(partionPoint < 0) {
        continue;
    }

    stack.push(partionPoint + 1);
    stack.push(sRight);

    stack.push(sLeft);
    stack.push(partionPoint - 1);
}

About Error

• 若產(chǎn)生無限循環(huán)松邪，則問題可能出在兩個方面：一個是遞歸終止條件；另一個是分割序列處的循環(huán)哨查，尤其注意forePoint和backPoint同時分別遇到與基準值相等的元素時逗抑，forePoint和backPoint的移動情況

• 若沒有正確排序，由于結(jié)果基本有序解恰，我們可以從錯誤序列中看出端倪锋八。如以下情況：

  Before:
  8 3 15 13 2 0 0 5 10 2 1 9 7 3 9 10 15 5 8 2 9 12 1 8 10
  After:
  0 0 1 1 2 2 2 3 3 5 5 7 8 8 9 8 9 9 10 10 10 12 13 15 15

共有25個元素，下標14和15位置的元素沒有正確排序护盈。25的分割沿著出錯位置依次為
0~11 12 13~24挟纱； 13~17 18 19~24; 13~14 15 16~17。 即可知道是13~17這次快速排序發(fā)生差錯腐宋，從而進行仔細調(diào)試紊服。

More

[3] 中通過尾遞歸對快速排序C語言版優(yōu)化檀轨。關(guān)于尾遞歸，[4]講述得比較明了欺嗤。然而Java沒有實現(xiàn)尾遞歸優(yōu)化参萄。相對的，我們只能采取避免遞歸過深或者用迭代取代遞歸的方式煎饼。

It's important to note that this isn't a bug in the JVM. It's an optimization that can be implemented to help functional programmers who use recursion, which is much more common and normal in those languages. I recently spoke to Brian Goetz at Oracle about this optimization, and he said that it's on a list of things to be added to the JVM, but it's just not a high-priority item. For now, it's best to make this optimization yourself, if you can, by avoiding deeply recursive functions when coding a functional language on the JVM.

DualPivotQuicksort

Java中對于基本數(shù)據(jù)類型的排序算法通過DualPivotQuicksort實現(xiàn)讹挎。它有如下特性：This algorithm offers O(n log(n)) performance on many data sets that cause other quicksorts to degrade to quadratic performance, and is typically faster than traditional (one-pivot) Quicksort implementations.

DualPivotQuicksort

排序方式具體如下：

1. For small arrays (length < 17), use the Insertion sort algorithm.
2. Choose two pivot elements P1 and P2. We can get, for example, the first element a[left] as P1 and the last element a[right] as P2.
3. P1 must be less than P2, otherwise they are swapped. So, there are the following parts:

• part I with indices from left+1 to L–1 with elements, which are less than P1,
• part II with indices from L to K–1 with elements, which are greater or equal to P1 and less or equal to P2,
• part III with indices from G+1 to right–1 with elements greater than P2,
• part IV contains the rest of the elements to be examined with indices from K to G.

4. The next element a[K] from the part IV is compared with two pivots P1 and P2, and placed to the corresponding part I, II, or III.
5. The pointers L, K, and G are changed in the corresponding directions.
6. The steps 4 - 5 are repeated while K ≤ G.
7. The pivot element P1 is swapped with the last element from part I, the pivot element P2 is swapped with the first element from part III.
8. The steps 1 - 7 are repeated recursively for every part I, part II, and part III.

性能比較

單位：nanosecond
環(huán)境：CPU 4核8線程 2.30GHZ
測試序列：長度100范圍0~100的隨機數(shù)序列

代碼地址

參考文獻

1 Mark Allen Weiss[美]. 數(shù)據(jù)結(jié)構(gòu)與算法分析: Java語言描述:第2版[M]. 機械工業(yè)出版社, 2012.
2 ThomasH.Cormen…. 算法導論:第2版[M]. 機械工業(yè)出版社, 2007.
3 http://blog.csdn.net/insistgogo/article/details/7785038
4 http://www.ruanyifeng.com/blog/2015/04/tail-call.html
5 http://stackoverflow.com/questions/20917617/whats-the-difference-of-dual-pivot-quick-sort-and-quick-sort