最近在複習資料結構與演算法，聊聊快速排序的幾種劃分演算法。

快速排序思路

快速排序是一種基於分治策略的排序演算法。

對於待排序陣列，其核心操作是：

  1. 選取一個基準數pivot
  2. 將陣列分為兩塊，一塊小於等於基準數，另一塊大於等於基準數（注意 基準數作為分界點）
  3. 遞迴地對於分出來的兩個數字再次進行快速排序

不斷地進行劃分，遞迴，最後能保證整個陣列有序。

基準數的選取

一般來說，基準數有幾種選取方法：

  1. 選取第一個數或者最後一個數：這樣做，如果陣列已經排好序，則每次劃分都是基準數和剩餘數，時間複雜度升至O(n^2)
  2. 隨機選擇一個數
  3. 選取中位數：這樣做始終能對原陣列進行等分，尋找中位數是線性時間的。

下面以最無腦的方法1為例。

幾種劃分方法

主要的劃分方法有：

  1. 樸素劃分
  2. Lomuto 劃分
  3. 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);
}