快速排序 幾種劃分方法討論

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

快速排序思路

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

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

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

基準數的選取

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

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

幾種劃分方法

主要的劃分方法有： 1. 樸素劃分 2. Lomuto 劃分 3. Hoare 劃分

中國大陸教材中經常出現的是第三種，即 Hoare 劃分，也叫哨兵劃分。

樸素劃分

思路很無腦。直接開一個新陣列，把比 pivot 小的放左邊，比 pivot 大的放右邊，最後把陣列複製回到原陣列。需要 O(n) 的額外空間。

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];
    }  // 先將小於等於 pivot 的複製進入

    int pid = idx;
    tmp[idx++] = pivot;

    for (int i = left; i <= right; i++) {
        if (A[i] > pivot)
            tmp[idx++] = A[i];
    }  // 再將大於 pivot 的複製進入

    for (int i = left; i <= right; i++) {
        A[i] = tmp[i];
    } // 複製回到 A

    return pid;
}

Lomuto 劃分

Lomuto 劃分即使用單個指標，從左到右掃描陣列，交換，維持劃分順序。

int Lomuto_Partition(int left, int right) {
    int pivot = A[right];
  
    int i = left - 1; // 維護的劃分中最右側的比 pivot 小的元素的下標

    // 遍歷陣列，把所有比 pivot 小的元素全部移動到左邊
    for (int j = left; j <= right - 1; j++) {  // 遍歷到 right - 1 可以對 pivot 進行保護，使得 pivot 不與自己對比，使邏輯更清晰，但或許沒必要
        if (A[j] < pivot) {
            i++;
            swap(A[i], A[j]);
        } // j 維護的是遍歷時下標，當發現一個比 pivot 小的數時，如果 i + 1 == j 則不動，否則說明之前存在一個數比 `pivot` 大需要交換，則及時進行交換
    }
    
    // 把 pivot 移回來
    swap(A[i + 1], A[right]);  
    return i + 1;
}

Hoare 劃分

Hoare 劃分採用雙指標，進行交換。

int Hoare_Partition(int left, int right) {
    int pivot = A[left];
    int pid = left;
    while (left < right) {
        while (left < right && A[right] >= pivot) {
            right--;
        } // 先從右往左掃描，保護 pivot
        while (left < right && A[left] <= pivot) {
            left++;
        } // 再從左往右掃描
        swap(A[left], A[right]); // 交換不正確的數
    }
    // 跳出迴圈時，left = right 說明找到了 pivot 的位置
    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 有

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);
}