快速排序（Quicksort）是對冒泡排序的一種改進(jìn)。由C. A. R. Hoare在1962年提出。它的基本思想是：通過一趟排序?qū)⒁判虻臄?shù)據(jù)分割成獨(dú)立的兩部分，其中一部分的所有數(shù)據(jù)都比另外一部分的所有數(shù)據(jù)都要小，然后再按此方法對這兩部分?jǐn)?shù)據(jù)分別進(jìn)行快速排序，整個排序過程可以遞歸進(jìn)行，以此達(dá)到整個數(shù)據(jù)變成有序序列。
public static void main(String[] args) {
// int[] p = { 34, 34, 54, 21, 54, 18, 23, 76, 38, 98, 45, 33, 27, 51,
// 11, 20, 79, 30, 89, 41 };
int[] p = { 34, 11, 10, 79, 41, 51, 23 };
printerInfo(p, 0, p.length - 1);
System.out.println("------------------------");
long start = System.currentTimeMillis();
Sort.qsort(p, 0, p.length - 1);// 快速排序
System.out.println("所用時間：" + (System.currentTimeMillis() - start));
printerInfo(p, 0, p.length - 1);
}
private static void printerInfo(int[] arr, int low, int high) {
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
System.out.println("[" + low + "," + high + "]");
}
private static void qsort(int[] arr, int low, int high) {
if (low < high) {
int pivot = partition(arr, low, high); // 將數(shù)組分為兩部分
qsort(arr, low, pivot - 1); // 遞歸排序左子數(shù)組
qsort(arr, pivot + 1, high); // 遞歸排序右子數(shù)組
}
}
private static int partition(int[] arr, int low, int high) {
int pivot = arr[low]; // 樞軸記錄
while (low < high) {
while (low < high && arr[high] >= pivot)
--high;
arr[low] = arr[high]; // 交換比樞軸小的記錄到左端
while (low < high && arr[low] <= pivot)
++low;
arr[high] = arr[low]; // 交換比樞軸大的記錄到右端
printerInfo(arr, low, high);
}
// 掃描完成，掃描的長度為一開始的(high-low),但是此時low=high，樞軸到位
arr[low] = pivot;
// printerInfo(arr, low, high);
// 返回的是樞軸的位置
return low;
}
算法性能/復(fù)雜度
可以看出，每一次調(diào)用partition()方法都需要掃描一遍數(shù)組長度（注意，在遞歸的時候這個長度并不是原數(shù)組的長度n，而是被分隔出來的小數(shù)組，即n*(2(-i))），其中i為調(diào)用深度。而在這一層同樣長度的數(shù)組有2i個。那么，每層排序大約需要O(n)復(fù)雜度。而一個長度為n的數(shù)組，調(diào)用深度最多為log(n)層。二者相乘，得到快速排序的平均復(fù)雜度為O(n ㏒n)。
通常，快速排序被認(rèn)為是在所有同數(shù)量級的排序方法中，平均性能最好。
從代碼中可以很容易地看出，快速排序單個棧的空間復(fù)雜度不高，每次調(diào)用partition方法時，其額外開銷只有O(1)。所以，最好情形下快速排序空間復(fù)雜度大約為O(㏒n)。
