- 快速排序為應(yīng)用最多的排序算法隘道，因為快速二字而聞名∧ㄖ瘢快速排序和歸并排序一樣怜瞒，采用的都是分治思想父泳。
- 分治法的基本思想是：將原問題分解為若干個規(guī)模更小但結(jié)構(gòu)與原問題相似的子問題。遞歸地解這些子問題吴汪，然后將這些子問題的解組合為原問題的解惠窄。
- 我們只需關(guān)注最小問題該如何求解，和如何去遞歸既可以得到正確的算法實現(xiàn)漾橙。
- 快速排序可以分為：單路快速排序杆融，雙路快速排序，三路快速排序近刘，他們區(qū)別在于選取幾個指針來對數(shù)組進(jìn)行遍歷下面我們依次來講解擒贸。
1. 單路快速算法
1.1 單路快速算法的思想：
image
首先我們選取數(shù)組中的一個數(shù)臀晃，將其放在合適的位置，這個位置左邊的數(shù)全部小于該數(shù)值介劫，這個位置右邊的數(shù)全部大于該數(shù)值 徽惋。
- 假設(shè)數(shù)組為 arr[l...r] 假設(shè)指定數(shù)值為數(shù)組第一個元素 int v = arr[l]，假設(shè) j 標(biāo)記為比 v 小的最后一個元素座韵， 即 arr[j+1] > v险绘。當(dāng)前考察的元素為 i 則有arr[l + 1 ... j] < v ， arr[j+1,i) >= v 如上圖所示誉碴。
- 假設(shè)正在考察的元素值為 e 宦棺，e >= v 的時候我們只需交將不動，直接 i++ 去考察下一個元素黔帕，
- 當(dāng)e < v 由上述假設(shè)我們需要將 e 放在<v 的部分 代咸，此時我們只需將 arr[j] 和 arr[i] 交換一下位置即可。
- 最后一個元素考察完成以后成黄，我們再講 arr[l]和 arr[j]調(diào)換一下位置就可以了呐芥。
- 上述遍歷完成以后 arr[l + 1 ... j] < v ， arr[j+1,i) >= v 就滿足了奋岁，接下來我們只需要遞歸的去考察 arr[l + 1 ... j] 和 arr[j+1,r] 即可思瘟。
1.2 單路快速排序的 Java 實現(xiàn):
public static void quickSortOneWay(int[] arr, int l, int r) {
if (l >= r) {
return;
}
int p = partition(arr, l, r);
quickSortOneWay(arr, l, p - 1);
quickSortOneWay(arr, p + 1, r);
}
private static int partition(int[] arr, int l, int r) {
// 為了提高效率，減少造成快速排序的遞歸樹不均勻的概率闻伶，
// 對于一個數(shù)組滨攻，每次隨機(jī)選擇的數(shù)為當(dāng)前 partition 操作中最小最大元素的可能性為 1/n
int randomNum = (int) (Math.random() * (r - l + 1) + l);
swap(arr, l, randomNum);
//將小于v的數(shù)據(jù)放在索引為j的位置
int v = arr[l];
int j = l;
for (int i = l + 1; i <= r; i++) {
if (arr[i] < v) {
swap(arr, j + 1, i);
j++;
}
}
swap(arr, l, j);
return j;
}
//交換位置
private static void swap(int[] arr, int l, int r) {
int temp = arr[l];
arr[l] = arr[r];
arr[r] = temp;
}
對于上述算法中為什么選取了當(dāng)前排序數(shù)組中隨機(jī)一個元素進(jìn)行比較，假設(shè)我們在考察的數(shù)組已經(jīng)為已經(jīng)排序好的數(shù)組蓝翰，那么我們遞歸樹就會向右側(cè)延伸 N 的深度光绕，這種情況使我們不想要看到的，如果我們每次 partition 都隨機(jī)從數(shù)組中取一個數(shù)霎箍，那么這個數(shù)是當(dāng)前排序數(shù)組中最小元素可能性為 1/n 那么每次都取到最小的數(shù)的可能性就很低了奇钞。
2雙路快速排序
2.1 雙路快速排序算法思想：
- 跟單路一樣，雙路快速排序漂坏，同樣選擇數(shù)組的第一個元素當(dāng)做標(biāo)志位（經(jīng)過隨機(jī)選擇后的）
- 雙路快速排序要求有兩個指針，指針 i j 分別指向 l+1 和 r 的位置然后兩者同時向數(shù)組中間遍歷 在遍歷過程中要保證arr[l+1 ... i) <= v媒至， arr(j....r] >= v 因此我們可以初始化 i = l+1 以保證左側(cè)區(qū)間初始為空顶别，j = r 保證右側(cè)空間為空
- 遍歷過程中要 i <= r 且 arr[i] <= v 的時候 i ++ 就可以了
當(dāng) arr[i] > v 時表示遇到了 i 的值大于 v 數(shù)值 此刻能等待 j 角標(biāo)的值，從右向左遍歷數(shù)組 當(dāng) arr[i] < v 表示遇到了 j 的值小于 v 的元素拒啰，它不該在這個位置呆著驯绎， - 得到了 i j 的角標(biāo)后 先要判斷是否到了循環(huán)結(jié)束的時候了，即 i 是否已經(jīng) 大于 j 了谋旦。
- 否則 應(yīng)該講 i 位置的元素和 j 位置的元素交換位置剩失，然后 i++ j-- 繼續(xù)循環(huán)
-
遍歷結(jié)束的條件是 i>j 此時 arr[j]為最后一個小于 v 的元素 arr[i] 為第一個大于 v 的元素 因此 j 這個位置 就應(yīng)該是 v 所應(yīng)該在數(shù)組中的位置 因此遍歷結(jié)束后需要交換 arr[l] 與 arr[j]
image
2.2 雙路快速排序的 Java 實現(xiàn):
public static void quickSortOneWay(int[] arr, int l, int r) {
if (l >= r) {
return;
}
int p = partition(arr, l, r);
quickSortOneWay(arr, l, p - 1);
quickSortOneWay(arr, p + 1, r);
}
private static int partition(int[] arr, int l, int r) {
// 為了提高效率屈尼，減少造成快速排序的遞歸樹不均勻的概率，
// 對于一個數(shù)組拴孤，每次隨機(jī)選擇的數(shù)為當(dāng)前 partition 操作中最小最大元素的可能性為 1/n
int randomNum = (int) (Math.random() * (r - l + 1) + l);
swap(arr, l, randomNum);
//將小于v的數(shù)據(jù)放在索引為j的位置
int v = arr[l];
int i = l;
int j = r;
while (true) {
while (i < r && arr[i] <= v) i++;
while (j > l + 1 && arr[j] >= v) j--;
if (i > j) {
break;
}
swap(arr, i, j);
i++;
j--;
}
swap(arr, l, j);
return j;
}
//交換位置
private static void swap(int[] arr, int l, int r) {
int temp = arr[l];
arr[l] = arr[r];
arr[r] = temp;
}
3 三路快速排序
3.1 三路快速排序算法思想
上述兩種算法我們發(fā)現(xiàn)對于與標(biāo)志位相同的值得處理總是脾歧，做了多余的交換處理，如果我們能夠?qū)?shù)組分為> = <三部分的話效率可能會有所提高演熟。
- 我們將數(shù)組劃分為 arr[l+1...lt] <v arr[lt+1..i) =v arr[gt...r] > v三部分 其中 lt 指向 < v 的最后一個元素前一個元素鞭执，gt 指向>v的第一個元素的前一個元素，i 為當(dāng)前考察元素
- 定義初始值得時候依舊可以保證這初始的時候這三部分都為空 int lt = l; int gt = r; int i = l + 1;
- 當(dāng) e > v 的時候我們需要將 arr[i] 與 arr[gt-1] 交換位置芒粹，并將 > v 的部分?jǐn)U大一個元素 即 gt-- 但是此時 i 指針并不需要操作兄纺，因為換過過來的數(shù)還沒有被考察。
- 當(dāng) e = v 的時候 i ++ 繼續(xù)考察下一個
- 當(dāng) e < v 的時候我們需要將 arr[i] 與 arr[lt+1] 交換位置
-
當(dāng)循環(huán)結(jié)束的時候 lt 位于小于 v 的最后一個元素位置所以最后我們需要將arr[l] 與 arr[lt] 交換一下位置化漆。
image
image
3.2 三路快速排序 Java 代碼實現(xiàn)：
@Override
public void quickSort(int[] arr, int left, int right) {
if (left >= right) {
return;
}
// 為了提高效率估脆，減少造成快速排序的遞歸樹不均勻的概率，
// 對于一個數(shù)組座云，每次隨機(jī)選擇的數(shù)為當(dāng)前 partition 操作中最小最大元素的可能性 降低 1/n!
int randomNum = (int) (Math.random() * (right - left + 1) + left);
swap(arr, left, randomNum);
int v = arr[left];
// 三路快速排序即把數(shù)組劃分為大于 小于 等于 三部分
//arr[l+1...lt] <v arr[lt+1..i) =v arr[gt...r] > v 三部分
// 定義初始值得時候依舊可以保證這初始的時候這三部分都為空
int leftEnd = left;
int rightStart = right;
int i = left + 1;
while (i <= rightStart) {
if (arr[i] < v) {
swap(arr, i, leftEnd + 1);
i++;
leftEnd++;
} else if (arr[i] == v) {
i++;
} else {
swap(arr, i, rightStart);
rightStart--;
//i++ 注意這里 i 不需要加1 因為這次交換后 i 的值仍不等于 v 可能小于 v 也可能等于 v 所以交換完成后 i 的角標(biāo)不變
}
}
swap(arr, left, leftEnd);
leftEnd--;
quickSort(arr, left, leftEnd);
quickSort(arr, rightStart, right);
}
4 快速排序時間復(fù)雜度空間復(fù)雜度
4.1 時間復(fù)雜度
- 在最優(yōu)的情況下旁蔼，快速排序算法的時間復(fù)雜度為O(nlogn)。
- 在最壞的情況下疙教，待排序的序列為正序或者逆序最終其時間復(fù)雜度為O(n2)棺聊。
- 平均的情況，設(shè)樞軸的關(guān)鍵字應(yīng)該在第k的位置（1≤k≤n）贞谓，那么：由數(shù)學(xué)歸納法可證明限佩，其數(shù)量級為O(nlogn)。
4.2 空間復(fù)雜度
就空間復(fù)雜度來說裸弦，主要是遞歸造成的椝钔空間的使用
- 最好情況，遞歸樹的深度為log2n理疙，其空間復(fù)雜度也就為O(logn)
- 最壞情況晕城，需要進(jìn)行n‐1遞歸調(diào)用，其空間復(fù)雜度為O(n)
- 平均情況窖贤，空間復(fù)雜度也為O(logn)砖顷。
可惜的是，由于關(guān)鍵字的比較和交換是跳躍進(jìn)行的滤蝠，因此，快速排序是一種不穩(wěn)定的排序方法授嘀。
