1.概述
排序和查找是程序設(shè)計里的兩類非常基本的問題，而現(xiàn)在也存在很多經(jīng)典的算法用于解決這兩類問題，本文主要對java中排序算法實現(xiàn)進(jìn)行一個基本的探討，希望能夠起到拋磚引玉的作用。在此之前，首先問各位幾個問題：你能寫出一個正確的快排嗎？快排在什么情況下真正的快？你的快排足夠快嗎？還可以進(jìn)一步優(yōu)化嗎？帶著這些問題，我們來看看jre7中快排是如何實現(xiàn)的吧。

Jre7中排序的實現(xiàn)類是DualPivotQuickSort.java，相比jre6有一些改變，主要發(fā)生在兩個地方，一個是insertion sort的實現(xiàn)上，另一個是QuickSort實現(xiàn)中pivot從一個變成了兩個。我們以int型的數(shù)組為例，該類中有個排序?qū)崿F(xiàn)的核心方法，該方法的原型為

參數(shù)a為需要排序的數(shù)組，left代表需要排序的數(shù)組區(qū)間中最左邊元素的索引，right代表區(qū)間中最右邊元素的索引，leftmost代表該區(qū)間是否是數(shù)組中最左邊的區(qū)間。舉個例子：
數(shù)組：[2, 4, 8, 5, 6, 3, 0, -3, 9]可以分成三個區(qū)間(2, 4, 8){5, 6}<3, 0, -3, 9>
對于()區(qū)間，left=0, right=2, leftmost=true
對于 {}區(qū)間, left=3, right=4, leftmost=false，同理可得<>區(qū)間的相應(yīng)參數(shù)

當(dāng)區(qū)間長度小于47時，該方法會采用插入排序；否則采用快速排序。

2. 插入排序?qū)崿F(xiàn)
當(dāng)leftmost為true時，它會采用傳統(tǒng)的插入排序(traditional insertion sort)，代碼也較簡單，其過程類似打牌時抓牌插牌：

傳統(tǒng)插入排序代碼
當(dāng)leftmost為false時，它采用一種新型的插入排序（pair insertion sort），改進(jìn)之處在于每次遍歷前面已排好序的數(shù)組需要插入兩個元素，而傳統(tǒng)插入排序在遍歷過程中只需要為一個元素找到合適的位置插入。對于插入排序來講，其關(guān)鍵在于為待插入元素找到合適的插入位置，為了找到這個位置，需要遍歷之前已經(jīng)排好序的子數(shù)組，所以對于插入排序來講，整個排序過程中其遍歷的元素個數(shù)決定了它的性能。很顯然，每次遍歷插入兩個元素可以減少排序過程中遍歷的元素個數(shù)，其實現(xiàn)代碼如下：

現(xiàn)在有個問題：為什么最左邊的區(qū)間采用傳統(tǒng)插入排序，其他的采用成對插入排序呢？加入用上述成對插入排序代碼替換傳統(tǒng)插入排序代碼，會出現(xiàn)什么問題呢？期待大家自己來回答。。。
3. 快速排序?qū)崿F(xiàn)
Jre7中對快速排序也做了改進(jìn)，傳統(tǒng)的快速排序是選取一個pivot（jre6種選取pivot的方法是挑選出數(shù)組最左邊，中間和最右邊位置的元素，將其中數(shù)值大小排在中間的元素作為pivot），然后分別從兩端向中間遍歷，把左邊遍歷過程中遇到的大于pivot的值和右邊遍歷中遇到的小于等于pivot的值進(jìn)行交換，當(dāng)遍歷相遇后，插入pivot的值；這樣就使得pivot左邊的值均小于或等于pivot，pivot右邊的值大于pivot；接下來再采用遞歸的方式對左邊和右邊分別進(jìn)行排序。

通過上述分析，我們可以看到：插入排序的每一步是使數(shù)組的一個子區(qū)間絕對有序，而每一次循環(huán)的本質(zhì)是使這個子區(qū)間不斷擴(kuò)大，所以我們可以看到其優(yōu)化的方向是使每次循環(huán)遍歷盡可能的使子區(qū)間擴(kuò)大的速度變快，所以上面把每次遍歷插入一個元素優(yōu)化成每次插入兩個元素。當(dāng)然肯定有人會問，那為什么不把這個數(shù)字變得更大一點呢？比如每次遍歷插入5個，10個。。。很顯然，這樣是不行，它的一個極端情況就是每次遍歷插入n個（n為數(shù)組長度）。。。至于為什么，大家自己回答吧。

對于快速排序來講，其每一次遞歸所做的是使需要排序的子區(qū)間變得更加有序，而不是絕對有序；所以對于快速排序來說，其性能決定于每次遞歸操作使待排序子區(qū)間變得有序的程度，另一個決定因素當(dāng)然就是遞歸次數(shù)。快速排序使子區(qū)間變得相對有序的關(guān)鍵是pivot，所以我們優(yōu)化的方向也應(yīng)該在于pivot，那就增加pivot的個數(shù)吧，而且我們可以發(fā)現(xiàn)，增加pivot的個數(shù)，對遞歸次數(shù)并不會有太大影響，有時甚至可以使遞歸次數(shù)減少。和insert sort類似的問題就是，pivot增加為幾個呢？很顯然，pivot的值也不能太大；記住，任何優(yōu)化都是有代價的，而增加pivot的代價就隱藏在每次交換元素的位置過程中。關(guān)子貌似賣的有點大了。。。下面我們就來看看pivot的值為2時，快速排序是如何實現(xiàn)的吧。其實現(xiàn)過程其實也不難理解：
1.  首先選取兩個pivot，pivot的選取方式是將數(shù)組分成近視等長的六段，而這六段其實是被5個元素分開的，將這5個元素從小到大排序，取出第2個和第4個，分別作為pivot1和pivot2；
2.  Pivot選取完之后，分別從左右兩端向中間遍歷，左邊遍歷停止的條件是遇到一個大于等于pivot1的值，并把那個位置標(biāo)記為less；右邊遍歷的停止條件是遇到一個小于等于pivot2的值，并把那個位置標(biāo)記為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.  完成上述過程之后，帶排序的子區(qū)間就被分成了三段（<pivot1, pivot1<=&&<=pivot2,>pivot2），最后分別對這三段采用遞歸就行了。

Jre7中對排序?qū)崿F(xiàn)的核心內(nèi)容就如上所述，具體細(xì)節(jié)可參見相應(yīng)類中的代碼，如發(fā)現(xiàn)錯誤或不妥之處，望指正。