快速排序( Quick Sort) 的基本思想是：通過一趟排序?qū)⒋庞涗浄指畛瑟?dú)立的兩部分松嘶，其中一部分記錄的關(guān)鍵字均比另一部分記錄的關(guān)鍵字小达址，則可分別對這兩部分記錄繼續(xù)進(jìn)行排序英古，以達(dá)到整個(gè)序列有序的目的衡招。
快速排序?qū)嶋H是一種交換排序炸茧，排序方法如圖1所示
圖1 快速排序
第一步：將left指針指向的數(shù)字緩存到base中二驰，right指針向左遍歷扔罪。如果right指針指向的數(shù)字小于base值，則將其賦值給left指針指向的位置桶雀；
第二步：left指針向右遍歷矿酵，如果left指針指向的數(shù)字大于base值，則將其賦值給right指針指向的位置矗积；
第三步：不斷重復(fù)第一全肮，第二步，直到left指針和right指針重合棘捣。
通過一趟排序?qū)⒁判虻臄?shù)據(jù)分割成獨(dú)立的兩部分：分割點(diǎn)左邊都是比它小的數(shù)辜腺，右邊都是比它大的數(shù)。然后再對分割點(diǎn)左右兩部分不斷重復(fù)上述一乍恐、二评疗、三步。
//快速排序
private static void quickSort(int[] a, int left, int right) {
//左下標(biāo)一定要小于又下標(biāo)茵烈，否則就數(shù)組越界
if (left < right) {
//對數(shù)組進(jìn)行分割排序百匆，返回分割點(diǎn)
int base = division( a, left, right );
//對左右兩部分，分別進(jìn)行遞歸排序
quickSort( a, left, base -1);
quickSort( a, base + 1, right );
}
}
private static int division(int[] a, int left, int right) {
//將第一個(gè)left指針設(shè)置為基準(zhǔn)base值
int base = a[left];
//當(dāng)左右指針重合時(shí)跳出循環(huán)
while (left < right) {
//如果right指針指向的值大于base呜投，繼續(xù)向左遍歷
while (left < right && a[right] >= base) {
right --;
}
//直到右指針指向的值小于base值或者遍歷結(jié)束（左右指針重合）加匈，
//將right指針指向的值賦值給left指針指向的位置
a[left] = a[right];
//如果left指針指向的值大于base，繼續(xù)向右遍歷
while (left < right && a[left] <= base) {
left ++;
}
//直到右指針指向的值小于base值或者遍歷結(jié)束（左右指針重合）仑荐，
//將right指針指向的值賦值給left指針指向的位置
a[right] = a[left];
}
//最后將base放置到left位置雕拼。此時(shí)left左側(cè)都比left值小，右側(cè)比left值大
a[left] = base;
return left;
}
public static void main(String[] args) {
int[] a = {1, 4 , 6, 0, 3, 2, 5, 9};
//調(diào)用快速排序释漆，設(shè)置初始的left指針和right指針
quickSort( a, 0, a.length-1);
System.out.print("Quick sort:\n");
for(int i=0; i<a.length; i++) {
System.out.print(a[i] + ", ");
}
}
輸出結(jié)果
Quick sort:
0, 1, 2, 3, 4, 5, 6, 9,
時(shí)間復(fù)雜度：O(nlogn)
