一，快速排序介紹
快速排序與歸並排序一樣，也是基於分治的遞歸算法，體現在：在每一趟快速排序中，需要選出樞軸元素，然後將比樞軸元素大的數組元素放在樞軸元素的右邊，比樞軸元素小的數組元素都放在樞軸元素的左邊。然後，再對分別對 樞軸元素左邊 和 樞軸元素右邊的元素進行快速排序。
二，快速排序算法分析
①相比於直接插入排序，快排合適於數據量大（上百萬）的情形，而插入排序適合於小數據量的情形。因為，在數據量小的情形下，快排的遞歸是需要一定的開銷的。
②相比於歸並排序，歸並排序的比較次數要比快速排序少，但是它需要一個額外的臨時數組，而且移動的元素多。而快速排序不需要顯示地聲明一個臨時數組，它用的是遞歸棧。在C++四使用它來作為標准的排序程序，而JAVA中則是用歸並排序來作為標准的排序。
③快速排序主要有兩個基本操作：一是選取樞軸元素，另一個則是遞歸分割數組。樞軸元素的選取對快速排序的效率至關重要，因為它決定了遞歸的深度。如果樞軸元素剛好處於數組的中間值，那麼，數組在分割時就分成了平均的兩部分。這樣的遞歸的效率就好。如果每次選取的樞軸元素都是最大/最小 的那個元素，則快排復雜度達到了O(N^2)，而且還用了遞歸棧空間。
④樞軸元素的選取可以采用三數取中法。所謂三數取中法，即給定一個數組，選取數組中的第一個元素，最後一個元素，和中間那個元素。哪個元素的值位於中間，則它作為樞軸元素。比如，a[0]=5 , a[4]=1, a[9]=10, 那麼 a[4]<a[0]<a[9] ，故a[0]是樞軸元素。
采用三數取中法時，會有一個問題，就是當數組不斷的遞歸劃分變小之後，樞軸左邊的元素個數不足3，這樣三數取中法就失去了應有的意義。此外，正如前面提到，對於小數組而言，插入排序反而比快速排序的效率更高。
正是基於以上兩個原因，我們可以將快速排序與插入排序結合。當遞歸劃分的數組變小之後，達到某個值（CUTOFF）時，采用插入排序。（代碼83行）
三，快速排序算法實現
public class QuickSort {
private static final int CUTOFF = 10;
/**
*
* @param arr
* 待排序的數組
*/
public static <T extends Comparable<? super T>> void quickSort(T[] arr) {
quickSort(arr, 0, arr.length - 1);
}
/**
* 快排的基本操作:通過三數取中法來選取樞軸元素
*
* @param arr
* 在[left, right]之間選擇pivot element
* @param left
* index of arr to chose pivot element
* @param right
* index of arr to chose pivot element
* @return pivot element
*/
private static <T extends Comparable<? super T>> T media3(T[] arr,
int left, int right) {
int center = (left + right) / 2;
if (arr[center].compareTo(arr[left]) < 0)
swapReference(arr, center, left);
if (arr[right].compareTo(arr[left]) < 0)
swapReference(arr, right, left);
// 參考前面兩個if比較之後,最小的元素被放置在
// arr[left],然後下面再比較中間與最右的元素,將最大的元素放在arr[right],而arr[center]存放中間元素(pivot)
if (arr[right].compareTo(arr[center]) < 0)
swapReference(arr, right, center);
swapReference(arr, center, right - 1);//將樞軸元素放在 arr[right-1]上.便於快排交換元素
return arr[right - 1];
}
private static <T extends Comparable<? super T>> void swapReference(
T[] arr, int from, int to) {
T tmp = arr[from];
arr[from] = arr[to];
arr[to] = tmp;
}
/**
* 實現了遞歸的快排主例程, internal quicksort method that makes recrusive calls
*
* @param arr
* an array of comparable items
* @param left
* the left-most index of subarray
* @param right
* the right-most index of subarray
*/
private static <T extends Comparable<? super T>> void quickSort(T[] arr,
int left, int right) {
if(left + CUTOFF <= right)
{
T pivot = media3(arr, left, right);
//begin partitoning
int i = left, j = right - 1;//在media3中已經將比pivot小的元素放到了a[left]上，把pivot放到了arr[right-1]上,故下面的while中是 ++i 和 --j
for(;;)
{
while(arr[++i].compareTo(pivot) < 0){}
while(arr[--j].compareTo(pivot) > 0){}
if(i < j)
swapReference(arr, i, j);
else
break;
}
swapReference(arr, i, right - 1);//restore pivot
quickSort(arr, left, i - 1);
quickSort(arr, i + 1, right);
}else
//Do an insertion sort on the subarray
insertSort(arr, left, right);
}
}
①第3行CUTOFF定義當數組中元素個數為10以下時，采用插入排序。
②第11行的quickSort方法是快排對外提供的接口
③第26行的media3方法實現了三數取中選取樞軸元素。其實，它不僅僅返回了樞軸元素，它還改變了原數組：
1) 它將三個數中最大的那個數放在了數組末尾arr[right]---（比樞軸小的放在樞軸元素左邊）
2) 它將三個數中最小的那個數放在了數組的開頭arr[left]---（比樞軸大的放在樞軸元素右邊）
3) 它將三個數中的中間那個數（樞軸元素）放在了 arr[right-1]位置處！！！---（在第71-72行選取是否交換元素時可以不受樞軸影響）
這是快排算法實現的技巧。
④第61行的quickSort方法則是實現快速遞歸分割的主例程。首先在第65行選取樞軸元素，第71行，在數組左邊尋找比樞軸元素大的元素；第72行，在數組右邊尋找比樞軸元素小的元素，第73-74行將之進行交換。可以看出，這些語句實現得非常精巧：在循環中只有自增和自減操作，以及判斷語句，因此執行速度是很快的。
在media3中已經將比pivot小的元素放到了a[left]上，把pivot放到了arr[right-1]上,故下面的while中是 ++i 和 --j
⑤第73行if語句 當 i > j 時 表示一趟快排已經結束，第78行將樞軸元素放到它的最終位置。對於快排而言，每進行一趟，樞軸元素的位置就被唯一確定下來，以後都不再變。
⑥第79 和 80行，對樞軸元素左右兩個的子數組遞歸調用。這樣，將原問題，劃分成了兩個子問題。
可以寫出它們的遞歸表達式：T(N)=T(i)+T(N-i-1)+O(N)
⑦當 快速排序劃分的子數組足夠小時（CUTOFF），不再采用快速排序，而是用插入排序。這樣，進一步優化了快速排序的速度。
用到的插入排序實現如下：
private static <T extends Comparable<? super T>> void insertSort(T[] a, int left ,int right){
for(int p = left + 1; p <= right; p++)
{
T tmp = a[p];//保存當前位置p的元素，其中[0,p-1]已經有序
int j;
for(j = p; j > 0 && tmp.compareTo(a[j-1]) < 0; j--)
{
a[j] = a[j-1];//後移一位
}
a[j] = tmp;//插入到合適的位置
}
四，快速排序算法復雜度分析
①快速排序的時間復雜度與樞軸元素的選取息息相關。平均情況下，時間復雜度為O(NlogN)，最壞情況下為O(N^2)
②樞軸元素的選取有多種方式：比如上面提到的三數取中，也可以采用隨機化算法來選取。采用三數取中時，幾乎不會出現最壞的情況。相對基於內存排序的其他算法，快速的效率是很高的，它的時間復雜度的常數因子很小。大約是1.3，而歸並大約是1.4 ----不太確定。 1.3NlogN
③快排用到了遞歸，當數組元素個數很少時，遞歸的開銷就有點大了，故在程序中可將快排與插入排序結合起來。
