1.概述
排序和查找是程序設計里的兩類非常基本的問題，而現在也存在很多經典的算法用于解決這兩類問題，本文主要對java中排序算法實現進行一個基本的探討，希望能夠起到拋磚引玉的作用。在此之前，首先問各位幾個問題：你能寫出一個正確的快排嗎？快排在什么情況下真正的快？你的快排足夠快嗎？還可以進一步優化嗎？帶著這些問題，我們來看看jre7中快排是如何實現的吧。
Jre7中排序的實現類是DualPivotQuickSort.java，相比jre6有一些改變，主要發生在兩個地方，一個是insertion sort的實現上，另一個是QuickSort實現中pivot從一個變成了兩個。我們以int型的數組為例，該類中有個排序實現的核心方法，該方法的原型為
void sort(int[] a, int left, int right, boolean leftmost)
參數a為需要排序的數組，left代表需要排序的數組區間中最左邊元素的索引，right代表區間中最右邊元素的索引，leftmost代表該區間是否是數組中最左邊的區間。舉個例子：
數組：[2, 4, 8, 5, 6, 3, 0, -3, 9]可以分成三個區間(2, 4, 8){5, 6}<3, 0, -3, 9>
對于()區間，left=0, right=2, leftmost=true
對于 {}區間, left=3, right=4, leftmost=false，同理可得<>區間的相應參數
當區間長度小于47時，該方法會采用插入排序；否則采用快速排序。
2. 插入排序實現
當leftmost為true時，它會采用傳統的插入排序(traditional insertion sort)，代碼也較簡單，其過程類似打牌時抓牌插牌：
for (int i = left, j = i; i < right; j = ++i) {
int ai = a[i + 1];
while (ai < a[j]) {
a[j + 1] = a[j];
if (j-- == left) {
break;
}
}
a[j + 1] = ai;
}
傳統插入排序代碼
當leftmost為false時，它采用一種新型的插入排序（pair insertion sort），改進之處在于每次遍歷前面已排好序的數組需要插入兩個元素，而傳統插入排序在遍歷過程中只需要為一個元素找到合適的位置插入。對于插入排序來講，其關鍵在于為待插入元素找到合適的插入位置，為了找到這個位置，需要遍歷之前已經排好序的子數組，所以對于插入排序來講，整個排序過程中其遍歷的元素個數決定了它的性能。很顯然，每次遍歷插入兩個元素可以減少排序過程中遍歷的元素個數，其實現代碼如下：
for (int k = left; ++left <= right; k = ++left) {
int a1 = a[k], a2 = a[left];
if (a1 < a2) {
a2 = a1; a1 = a[left];
}
while (a1 < a[--k]) {
a[k + 2] = a[k];
}
a[++k + 1] = a1;
while (a2 < a[--k]) {
a[k + 1] = a[k];
}
a[k + 1] = a2;
}
現在有個問題：為什么最左邊的區間采用傳統插入排序，其他的采用成對插入排序呢？加入用上述成對插入排序代碼替換傳統插入排序代碼，會出現什么問題呢？期待大家自己來回答。。。
3. 快速排序實現
Jre7中對快速排序也做了改進，傳統的快速排序是選取一個pivot（jre6種選取pivot的方法是挑選出數組最左邊，中間和最右邊位置的元素，將其中數值大小排在中間的元素作為pivot），然后分別從兩端向中間遍歷，把左邊遍歷過程中遇到的大于pivot的值和右邊遍歷中遇到的小于等于pivot的值進行交換，當遍歷相遇后，插入pivot的值；這樣就使得pivot左邊的值均小于或等于pivot，pivot右邊的值大于pivot；接下來再采用遞歸的方式對左邊和右邊分別進行排序。
通過上述分析，我們可以看到：插入排序的每一步是使數組的一個子區間絕對有序，而每一次循環的本質是使這個子區間不斷擴大，所以我們可以看到其優化的方向是使每次循環遍歷盡可能的使子區間擴大的速度變快，所以上面把每次遍歷插入一個元素優化成每次插入兩個元素。當然肯定有人會問，那為什么不把這個數字變得更大一點呢？比如每次遍歷插入5個，10個。。。很顯然，這樣是不行，它的一個極端情況就是每次遍歷插入n個（n為數組長度）。。。至于為什么，大家自己回答吧。
對于快速排序來講，其每一次遞歸所做的是使需要排序的子區間變得更加有序，而不是絕對有序；所以對于快速排序來說，其性能決定于每次遞歸操作使待排序子區間變得有序的程度，另一個決定因素當然就是遞歸次數。快速排序使子區間變得相對有序的關鍵是pivot，所以我們優化的方向也應該在于pivot，那就增加pivot的個數吧，而且我們可以發現，增加pivot的個數，對遞歸次數并不會有太大影響，有時甚至可以使遞歸次數減少。和insert sort類似的問題就是，pivot增加為幾個呢？很顯然，pivot的值也不能太大；記住，任何優化都是有代價的，而增加pivot的代價就隱藏在每次交換元素的位置過程中。關子貌似賣的有點大了。。。下面我們就來看看pivot的值為2時，快速排序是如何實現的吧。其實現過程其實也不難理解：
1. 首先選取兩個pivot，pivot的選取方式是將數組分成近視等長的六段，而這六段其實是被5個元素分開的，將這5個元素從小到大排序，取出第2個和第4個，分別作為pivot1和pivot2；
2. Pivot選取完之后，分別從左右兩端向中間遍歷，左邊遍歷停止的條件是遇到一個大于等于pivot1的值，并把那個位置標記為less；右邊遍歷的停止條件是遇到一個小于等于pivot2的值，并把那個位置標記為great
3. 然后從less位置向后遍歷，遍歷的位置用k表示，會遇到以下幾種情況:
a. k位置的值比pivot1小，那就交換k位置和less位置的值，并是less的值加1；這樣就使得less位置左邊的值都小于pivot1，而less位置和k位置之間的值大于等于pivot1
b. k位置的值大于pivot2，那就從great位置向左遍歷，遍歷停止條件是遇到一個小于等于pivot2的值，假如這個值小于pivot1，就把這個值寫到less位置，把less位置的值寫道k位置，把k位置的值寫道great位置，最后less++，great--；加入這個值大于等于pivot1，就交換k位置和great位置，之后great—
4. 完成上述過程之后，帶排序的子區間就被分成了三段（<pivot1, pivot1<=&&<=pivot2,>pivot2），最后分別對這三段采用遞歸就行了。
/*
* Partitioning:
*
* left part center part right part
* +--------------------------------------------------------------+
* | < pivot1 | pivot1 <= && <= pivot2 | ? | > pivot2 |
* +--------------------------------------------------------------+
* ^ ^ ^
* | | |
* less k great
*
* Invariants:
*
* all in (left, less) < pivot1
* pivot1 <= all in [less, k) <= pivot2
* all in (great, right) > pivot2
*
* Pointer k is the first index of ?-part.
*/
Jre7中對排序實現的核心內容就如上所述，具體細節可參見相應類中的代碼，如發現錯誤或不妥之處，望指正。
