最近在複習資料結構與演算法，聊聊快速排序的幾種劃分演算法。
快速排序思路
快速排序是一種基於分治策略的排序演算法。
對於待排序陣列，其核心操作是：
- 選取一個基準數
pivot
- 將陣列分為兩塊，一塊小於等於基準數，另一塊大於等於基準數（注意 基準數作為分界點）
- 遞迴地對於分出來的兩個數字再次進行快速排序
不斷地進行劃分，遞迴，最後能保證整個陣列有序。
基準數的選取
一般來說，基準數有幾種選取方法：
- 選取第一個數或者最後一個數：這樣做，如果陣列已經排好序，則每次劃分都是基準數和剩餘數，時間複雜度升至
O(n^2)
- 隨機選擇一個數
- 選取中位數：這樣做始終能對原陣列進行等分，尋找中位數是線性時間的。
下面以最無腦的方法1為例。
幾種劃分方法
主要的劃分方法有：
- 樸素劃分
- Lomuto 劃分
- Hoare 劃分
中國大陸教材中經常出現的是第三種，即 Hoare 劃分，也叫哨兵劃分。
樸素劃分
思路很無腦。直接開一個新陣列，把比 pivot 小的放左邊，比 pivot 大的放右邊，最後把陣列複製回到原陣列。需要 O(n) 的額外空間。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
| const int N;
int A[N];
int tmp[N];
int Native_Partition(int left, int right) {
int pivot = A[left];
int idx = left;
for (int i = left; i <= right; i++) {
if (A[i] < pivot)
tmp[idx++] = A[i];
}
int pid = idx;
tmp[idx++] = pivot;
for (int i = left; i <= right; i++) {
if (A[i] > pivot)
tmp[idx++] = A[i];
}
for (int i = left; i <= right; i++) {
A[i] = tmp[i];
}
return pid;
}
|
Lomuto 劃分
Lomuto 劃分即使用單個指標，從左到右掃描陣列，交換，維持劃分順序。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| int Lomuto_Partition(int left, int right) {
int pivot = A[right];
int i = left - 1;
for (int j = left; j <= right - 1; j++) {
if (A[j] < pivot) {
i++;
swap(A[i], A[j]);
}
}
swap(A[i + 1], A[right]);
return i + 1;
}
|
Hoare 劃分
Hoare 劃分採用雙指標，進行交換。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| int Hoare_Partition(int left, int right) {
int pivot = A[left];
int pid = left;
while (left < right) {
while (left < right && A[right] >= pivot) {
right--;
}
while (left < right && A[left] <= pivot) {
left++;
}
swap(A[left], A[right]);
}
swap(A[pid], A[left]);
return pid;
}
|
掃描順序對於結果有影響。pivot 在最左邊時，應該先從右往左掃描。
如果先從左往右掃，找第一個大於 pivot 的數 a，而第一個小於 pivot 的數在 a 左側，此時進行 pivot 和 A[left] 的交換，會導致交換錯誤。故應該優先保證 pivot 左側都小於等於 pivot，即先尋找第一個小於 pivot 的數，這樣交換是安全的。
快速排序演算法
對於某劃分函式 partition(int st, int end) -> pivot: int 有
1
2
3
4
5
6
7
8
9
10
11
12
| const int N;
int A[N];
void qsort(int st, int end){
if(st >= end) return;
int pivot = partition(st, end);
qsort(st, pivot-1);
qsort(pivot+1, end);
}
|
