1. 經(jīng)典快速排序圖示過程
(1) 經(jīng)典快速排序的總體流程
(2) 根據(jù)基準值分區(qū)的過程
在[算法題] 荷蘭國旗問題中有詳細的介紹。
2. 隨機快速排序
經(jīng)典快速排序總是指定數(shù)組或者某部分的最后一個元素作為基準值吵聪，隨機快速排序指定數(shù)組或者某一部分中的隨機值作為基準值。
3. 動圖展示
quickSort.gif
4. 隨機快速排序Java代碼實現(xiàn)
/**
* 快速排序体箕，使得整數(shù)數(shù)組 arr 有序
*/
public static void quickSort(int[] arr) {
if (arr == null || arr.length < 2) {
return;
}
quickSort(arr, 0, arr.length - 1);
}
/**
* 快速排序柏副，使得整數(shù)數(shù)組 arr 的 [L, R] 部分有序
*/
public static void quickSort(int[] arr, int L, int R) {
if(L < R) {
// 把數(shù)組中隨機的一個元素與最后一個元素交換宛琅，這樣以最后一個元素作為基準值實際上就是以數(shù)組中隨機的一個元素作為基準值
swap(arr, new Random().nextInt(R - L + 1) + L, R);
int[] p = partition(arr, L, R);
quickSort(arr, L, p[0] - 1);
quickSort(arr, p[1] + 1, R);
}
}
/**
* 分區(qū)的過程，整數(shù)數(shù)組 arr 的[L, R]部分上蒋腮，使得：
* 大于 arr[R] 的元素位于[L, R]部分的右邊淘捡，但這部分數(shù)據(jù)不一定有序
* 小于 arr[R] 的元素位于[L, R]部分的左邊，但這部分數(shù)據(jù)不一定有序
* 等于 arr[R] 的元素位于[L, R]部分的中間
* 返回等于部分的第一個元素的下標和最后一個下標組成的整數(shù)數(shù)組
*/
public static int[] partition(int[] arr, int L, int R) {
int basic = arr[R];
int less = L - 1;
int more = R + 1;
while(L < more) {
if(arr[L] < basic) {
swap(arr, ++less, L++);
} else if (arr[L] > basic) {
swap(arr, --more, L);
} else {
L++;
}
}
return new int[] { less + 1, more - 1 };
}
/*
* 交換數(shù)組 arr 中下標為 i 和下標為 j 位置的元素
*/
public static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
5. 復雜度
- 時間復雜度：O(nlogn)
- 空間復雜度：快速排序使用遞歸池摧，遞歸使用棧焦除，因此它的空間復雜度為O(logn)
- 穩(wěn)定性：快速排序無法保證相等的元素的相對位置不變，因此它是不穩(wěn)定的排序算法
