Java 快速排序(QuickSort)原理及實現代碼

快速排序（QuickSort ）是常用到的效率比較高的一種排序算法，在面試過程中也經常提及。下面就詳細講解一下他的原理、給出一個Java版本的實現。

快速排序思想：

通過對數據元素集合Rn 進行一趟排序劃分出獨立的兩個部分。其中一個部分的關鍵字比另一部分的關鍵字小。然後再分別對兩個部分的關鍵字進行一趟排序，直到獨立的元素只有一個，此時整個元素集合有序。

快速排序的過程――挖坑填數法（這是一個很形象的名稱），對一個元素集合R[ low ... high ] ,首先取一個數（一般是R[low] ）做參照， 以R[low]為基準重新排列所有的元素。

所有比R[low]小的放前面，所有比R[low] 大的放後面，然後以R[low]為分界，對R[low ... high] 劃分為兩個子集和，再做劃分。直到low >= high 。

比如：對R={37, 40, 38, 42, 461, 5, 7, 9, 12}進行一趟快速排序的過程如下(注:下面描述的內容中元素下表從0 開始)：

開始選取基準base = 37，初始位置下表low = 0 ， high = 8 ， 從high=8，開始如果R[8] < base , 將high位置中的內容寫入到R[low]中, 將high位置空出來, low = low +1 ;

從low開始探測，由於low=1 ， R[low] > base ,所以將R[low]寫入到R[high] , high = high -1 ;

檢測到low < high ,所以第一趟快速排序仍需繼續:

此時low=1，high=7，因為R[high] < base ,所以將R[high] 寫入到到R[low]中,low = low + 1;

從low開始探測,low = 2 , R[low] >base ,所以講R[low]寫入到R[high]，high=high-1;

繼續檢測到low 小於high

此時low=2，high=6，同理R[high] < base ,將R[high] 寫入到R[low]中，low=low+1;

從low繼續探測,low = 3 , high=6 , R[low] > base , 將R[low]寫入到R[high]中，high = high-1;

繼續探測到low小於high

此時low=3，high=5，同理R[high] < base,將R[high]寫入到R[low]中，low = low +1；

從low繼續探測，low = 4，high=5，由於R[low] > base , 將R[low]寫入到R[high]中，high = high -1 ;

此時探測到low == high == 4 ；該位置即是base所在的位置，將base寫入到該位置中.

然後再對子序列Rs1 = {12,9,7,5} 和Rs2={461,42,38,40}做一趟快速排序，直到Rsi中只有一個元素，或沒有元素。

（注: 在以上表單中可以看到一趟排序中有一些重複的數據（原始數據中沒有重複的數據），這是因為沒有清除該位置的數據，我們在特定的時間看該內存塊的數據依然是它，直到下一次將數據寫入該位置位置―― 在此該位置的數據是一個沒有意義臟數據，稱之為“坑”）

快速排序的Java實現：

複製代碼代碼如下:

private static boolean isEmpty(int[] n) {

return n == null || n.length == 0;

}

// //////////////////////////////////////////////// ///

/**

* 快速排序算法思想――挖坑填數方法：

*

* @param n 待排序的數組

*/

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;

}

在代碼中有這樣一個函數：

複製代碼代碼如下:

public static void quickSortSwap(int[] n, int l, int h)

該函數可以實現，元素集合中特定的l 到h 位置間的數據元素進行排序。

關於快速排序就寫到這裡了。