快速排序（QuickSort ）是常用到的效率比較高的一種排序算法，在面試過程中也經(jīng)常提及。下面就詳細(xì)講解一下他的原理、給出一個(gè)Java版本的實(shí)現(xiàn)。
快速排序思想：
通過對(duì)數(shù)據(jù)元素集合Rn 進(jìn)行一趟排序劃分出獨(dú)立的兩個(gè)部分。其中一個(gè)部分的關(guān)鍵字比另一部分的關(guān)鍵字小。然后再分別對(duì)兩個(gè)部分的關(guān)鍵字進(jìn)行一趟排序，直到獨(dú)立的元素只有一個(gè)，此時(shí)整個(gè)元素集合有序。
快速排序的過程——挖坑填數(shù)法（這是一個(gè)很形象的名稱），對(duì)一個(gè)元素集合R[ low ... high ] ,首先取一個(gè)數(shù)（一般是R[low] ）做參照 ， 以R[low]為基準(zhǔn)重新排列所有的元素。
所有比R[low]小的放前面，所有比R[low] 大的放后面，然后以R[low]為分界，對(duì)R[low ... high] 劃分為兩個(gè)子集和，再做劃分。直到low >= high 。
比如：對(duì)R={37, 40, 38, 42, 461, 5, 7, 9, 12}進(jìn)行一趟快速排序的過程如下(注:下面描述的內(nèi)容中元素下表從 0 開始)：
|
原始序列 |
37 |
40 |
38 |
42 |
461 |
5 |
7 |
9 |
12 |
|
一：high-->low |
12 |
40 |
38 |
42 |
461 |
5 |
7 |
9 |
12 |
|
一：low --> high |
12 |
40 |
38 |
42 |
461 |
5 |
7 |
9 |
40 |
|
二：high-->low |
12 |
9 |
38 |
42 |
461 |
5 |
7 |
9 |
40 |
|
二：low --> high |
12 |
9 |
38 |
42 |
461 |
5 |
7 |
38 |
40 |
|
三：high --> low |
12 |
9 |
7 |
42 |
461 |
5 |
7 |
38 |
40 |
|
三：low -->high |
12 |
9 |
7 |
42 |
461 |
5 |
42 |
38 |
40 |
|
四：high --> low |
12 |
9 |
7 |
5 |
461 |
5 |
42 |
38 |
40 |
|
四：low --> high |
12 |
9 |
7 |
5 |
461 |
461 |
42 |
38 |
40 |
|
一趟排序結(jié)果 |
12 |
9 |
7 |
5 |
37 |
461 |
42 |
38 |
40 |
開始選取基準(zhǔn) base = 37，初始位置下表 low = 0 ， high = 8 ， 從high=8，開始如果R[8] < base , 將high位置中的內(nèi)容寫入到R[low]中, 將high位置空出來, low = low +1 ;
從low開始探測(cè)，由于low=1 ， R[low] > base ,所以將R[low]寫入到R[high] , high = high -1 ;
檢測(cè)到low < high ,所以第一趟快速排序仍需繼續(xù):
此時(shí)low=1，high=7，因?yàn)?R[high] < base ,所以將 R[high] 寫入到到R[low]中,low = low + 1;
從low開始探測(cè),low = 2 , R[low] >base ,所以講R[low]寫入到R[high]，high=high-1;
繼續(xù)檢測(cè)到 low 小于high
此時(shí)low=2，high=6，同理R[high] < base ,將R[high] 寫入到R[low]中，low=low+1;
從low繼續(xù)探測(cè),low = 3 , high=6 , R[low] > base , 將R[low]寫入到R[high]中，high = high-1;
繼續(xù)探測(cè)到low小于high
此時(shí)low=3，high=5，同理R[high] < base,將R[high]寫入到R[low]中，low = low +1；
從low繼續(xù)探測(cè)，low = 4，high=5，由于R[low] > base , 將R[low]寫入到R[high]中，high = high -1 ;
此時(shí)探測(cè)到low == high == 4 ；該位置即是base所在的位置，將base寫入到該位置中.
然后再對(duì)子序列Rs1 = {12,9,7,5} 和 Rs2={461,42,38,40}做一趟快速排序，直到Rsi中只有一個(gè)元素，或沒有元素。
（注: 在以上表單中可以看到一趟排序中有一些重復(fù)的數(shù)據(jù)（原始數(shù)據(jù)中沒有重復(fù)的數(shù)據(jù)），這是因?yàn)闆]有清除該位置的數(shù)據(jù)，我們?cè)谔囟ǖ臅r(shí)間看該內(nèi)存塊的數(shù)據(jù)依然是它，直到下一次將數(shù)據(jù)寫入該位置位置 —— 在此該位置的數(shù)據(jù)是一個(gè)沒有意義臟數(shù)據(jù)，稱之為 “坑”）
快速排序的Java實(shí)現(xiàn)：
private static boolean isEmpty(int[] n) {
return n == null || n.length == 0;
}
// ///////////////////////////////////////////////////
/**
* 快速排序算法思想——挖坑填數(shù)方法：
*
* @param n 待排序的數(shù)組
*/
public static void quickSort(int[] n) {
if (isEmpty(n))
return;
quickSort(n, 0, n.length - 1);
}
public static void quickSort(int[] n, int l, int h) {
if (isEmpty(n))
return;
if (l < h) {
int pivot = partion(n, l, h);
quickSort(n, l, pivot - 1);
quickSort(n, pivot + 1, h);
}
}
private static int partion(int[] n, int start, int end) {
int tmp = n[start];
while (start < end) {
while (n[end] >= tmp && start < end)
end--;
if (start < end) {
n[start++] = n[end];
}
while (n[start] < tmp && start < end)
start++;
if (start < end) {
n[end--] = n[start];
}
}
n[start] = tmp;
return start;
}
在代碼中有這樣一個(gè)函數(shù)：
public static void quickSortSwap(int[] n, int l, int h)
該函數(shù)可以實(shí)現(xiàn)，元素集合中特定的 l 到 h 位置間的數(shù)據(jù)元素進(jìn)行排序。
關(guān)于快速排序就寫到這里了。
