理解快速排序算法
快速排序在平均狀況下，排序n個項目要Ο(n log n)次比較。在最壞狀況下則需要Ο(n2)次比較，但這種狀況并不常見。事實上，快速排序通常明顯比 其他Ο(n log n)算法更快，因為它的內部循環（inner loop）可以在大部分的架構上很有效率地被實現出來。
快速排序使用分治法（Divide and conquer）策略來把一個序列（list）分為兩個子序列（sub-lists）。
步驟為：
1.從數列中挑出一個元素，稱為"基準"（pivot）， 2.重新排序數列，所有元素比基準值小的擺放在基準前面，所有元素比基準值大的擺在基準的后面（相同的數可以到任一邊）。在這個分區結束之后，該基準就處于數列的中間位置。這個稱為分區（partition ）操作。 3.遞歸地（recursive）把小于基準值元素的子數列和大于基準值元素的子數列排序。
效果圖如下：
partition方法
partition方法是快速排序算法的核心，下面先寫一個簡單的原地（in-place）分區的版本。
public class Test1 {
public static void main(String args[]) {
int[] a = {354,656,21,2342,65,657,76,12,54,778,50,31,333,45,56,86,97,121} ;
System.out.print(partition(a,2)) ;
}
static int partition(int arr[], int pivotIndex)
{
int start = 0 ;
int end = arr.length - 1 ;
int pivot = arr[pivotIndex];
swap(arr,pivotIndex, end);
int storeIndex = start;
for(int i = start; i < end; ++i) {
if(arr[i] < pivot) {
swap(arr,i, storeIndex);
++storeIndex;
}
}
swap(arr,storeIndex, end);
return storeIndex;
}
public static void swap ( int [] data, int a, int b) {
int t = data [a];
data [a] = data [b];
data [b] = t;
}
}
首先注意swap方法，swap方法用于交換數組中的兩個元素。
partition當中調用了三次swap，我們隨機選中一個位置作為"基準"（pivot）,第一次交換就是把這個pivot交換到數組最后一位。 第三次當然就是把它從最后一位交換到它應該在的位置。中間的for循環是這個方法的核心。
storeIndex就是最后pivot擺放的位置。storeIndex前面的元素都比pivot小，storeIndex之后的元素都比pivot大。 所以我們從第一個元素遍歷到最后一個，目的是把全部元素分成兩段，storeIndex位于兩段中間，第一段全部是是小于pivot的元素， 第二段都是大于pivot的元素，完成分段之后在把pivot從最后一個位置交換到兩段中間。 循環時發現元素小于pivot，就把元素移動到后半段子序列的開頭，然后把后半段開頭的標記位storeIndex＋1。這就是for循環里的工作。
要注意的是，一個元素在到達它的最后位置前，可能會被交換很多次。 下面對原地分區的版本進行優化如下：
static int partition(int arr[], int pivotIndex)
{
int start = 0 ;
int end = arr.length -1;
int mid = arr[pivotIndex];
int left = start, right = end - 1;
while (left < right) {
while (arr[left] < mid && left < right)
left++;
while (arr[right] >= mid && left < right)
right--;
swap(arr,left, right);
}
if (arr[left] >= arr[end])
swap(arr,left, end);
else
left++;
return left;
}
現在我們采用了兩個指針，對應兩個子while循環，一個從前向后遍歷，一個從后向前遍歷。從前向后遍歷時遇到大于基準數pivot的時候停止， 從后向前遍歷時遇到小于基準數pivot的時候停止，然后交換兩個數。
一旦我們有了這個分區算法，要寫快速排列本身就很容易。
完整的快排算法
public class Test2 {
static int[] arr ;
private static void swap(int x, int y) {
int temp = arr[x];
arr[x] = arr[y];
arr[y] = temp;
}
private static void quick_sort_recursive(int start, int end) {
if (start >= end)
return;
int mid = arr[end];
int left = start, right = end - 1;
while (left < right) {
while (arr[left] < mid && left < right)
left++;
while (arr[right] >= mid && left < right)
right--;
swap(left, right);
}
if (arr[left] >= arr[end])
swap(left, end);
else
left++;
quick_sort_recursive(start, left - 1);
quick_sort_recursive(left + 1, end);
}
public static void sort(int[] arrin) {
arr = arrin;
quick_sort_recursive(0, arr.length - 1);
}
public static void main(String args[]) {
int[] a = {354,656,21,2342,65,657,76,12,54,778,50,31,333,45,56,86,97,121} ;
sort(a);
System.out.print(Arrays.toString(arr));
}
}
算法分析
快速排序的時間主要耗費在劃分操作上，對長度為 k 的區間進行劃分，共需 k-1 次關鍵字的比較。
最壞時間復雜度
最壞情況是每次劃分選取的基準都是當前無序區中關鍵字最小(或最大)的記錄，劃分的結果是基準左邊的子區間為空(或右邊的子區間為空)， 而劃分所得的另一個非空的子區間中記錄數目，僅僅比劃分前的無序區中記錄個數減少一個。 因此，快速排序必須做 n-1 次劃分， 第i次劃分開始時區間長度為 n-i+1，所需的比較次數為 n-i(1≤i≤n-1)，故總的比較次數達到最大值：Cmax = n(n-1)/2=O(n2)
如果按上面給出的劃分算法，每次取當前無序區的第 1 個記錄為基準，那么當文件的記錄已按遞增序(或遞減序)排列時， 每次劃分所取的基準就是當前無序區中關鍵字最小(或最大)的記錄，則快速排序所需的比較次數反而最多。
最好時間復雜度
在最好情況下，每次劃分所取的基準都是當前無序區的"中值"記錄，劃分的結果是基準的左、右兩個無序子區間的長度大致相等。 總的關鍵字比較次數：O(nlgn)
注意： 用遞歸樹來分析最好情況下的比較次數更簡單。因為每次劃分后左、右子區間長度大致相等，故遞歸樹的高度為 O(lgn)， 而遞歸樹每一層上各結點所對應的劃分過程中所需要的關鍵字比較次數總和不超過n，故整個排序過程所需要的關鍵字比較總次數 C(n)=O(nlgn)。
因為快速排序的記錄移動次數不大于比較的次數，所以快速排序的最壞時間復雜度應為 O(n2)，最好時間復雜度為 O(nlgn)。
平均時間復雜度
盡管快速排序的最壞時間為 O(n2)，但就平均性能而言，它是基于關鍵字比較的內部排序算法中速度最快者，快速排序亦因此而得名。 它的平均時間復雜度為 O(nlgn)。
基準關鍵字的選取
在當前無序區中選取劃分的基準關鍵字是決定算法性能的關鍵。
1."三者取中"的規則
"三者取中"規則，即在當前區間里，將該區間首、尾和中間位置上的關鍵字比較，取三者之中值所對應的記錄作為基準， 在劃分開始前將該基準記錄和該區伺的第1個記錄進行交換，此后的劃分過程與上面所給的 Partition 算法完全相同。
2.取位于 low 和 high 之間的隨機數k(low≤k≤high)，用 R[k] 作為基準
選取基準最好的方法是用一個隨機函數產生一個取位于 low 和 high 之間的隨機數 k(low≤k≤high)，用 R[k] 作為基準， 這相當于強迫R[low..high]中的記錄是隨機分布的。用此方法所得到的快速排序一般稱為隨機的快速排序。
注意： 隨機化的快速排序與一般的快速排序算法差別很小。但隨機化后，算法的性能大大地提高了，尤其是對初始有序的文件， 一般不可能導致最壞情況的發生。算法的隨機化不僅僅適用于快速排序，也適用于其它需要數據隨機分布的算法。
空間復雜度
快速排序在系統內部需要一個棧來實現遞歸。若每次劃分較為均勻，則其遞歸樹的高度為 O(lgn)，故遞歸后需棧空間為 O(lgn)。 最壞情況下，遞歸樹的高度為 O(n)，所需的棧空間為 O(n)。