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中對排序實作的核心內容如上所述，具體細節可參考對應類別中的程式碼，如發現錯誤或不妥之處，望指正。