快速排序 C 語言實現：挖坑填數法與遞歸分治

快速排序核心思想

1. 選取基準數
2. 分區：小於基準者置左，大於等於基準者置右
3. 遞歸處理左右子區間，直到區間長度為 1

挖坑填數法詳細步驟

1. i = L, j = R，將基準數 x = a[L] 挖出形成第一個坑
2. j-- 從右向左找 小於 x 的數，填入 a[i]，形成新坑位於 j
3. i++ 從左向右找 大於等於 x 的數，填入 a[j]，形成新坑位於 i
4. 重複 2-3 直到 i == j，將基準數 x 填入 a[i]

完整代碼實現

#include 
#include 

void quick_sort(int s[], int l, int r);

int main(void) {
    int a[10] = {20, 8, 10, 27, 9, 22, 24, 7, 15, 55};
    quick_sort(a, 0, 9);
    for (int i = 0; i < 10; i++)
        printf("%d ", a[i]);
    printf("\n");
    return 0;
}

void quick_sort(int s[], int l, int r) {
    if (l < r) {
        int i = l, j = r, x = s[l];
        while (i < j) {
            while (i < j && s[j] >= x) j--;
            if (i < j) s[i++] = s[j];
            while (i < j && s[i] < x) i++;
            if (i < j) s[j--] = s[i];
        }
        s[i] = x;
        quick_sort(s, l, i - 1);
        quick_sort(s, i + 1, r);
    }
}

關鍵點分析

• 基準選取：此處取首元素，易於有序陣列退化 O(n²)。工程上常用「三數取中」或隨機選取優化
• 分區邊界：s[j] >= x、s[i] < x 保證相等元素聚右側，穩定性視實現而定
• 遞歸終止：l >= r 即區間長度 ≤ 1
• 空間複雜度：平均 O(log n)（遞歸棧），最差 O(n)

優化方向

1. 小區間改用插入排序（如 < 10 元素）
2. 尾遞歸優化：處理完較小分區後迴圈處理較大分區，減少棧深度
3. 三向切分：處理大量重複鍵值（Dutch National Flag）
4. 隨機化基準：消除最壞情況依賴輸入分佈

複雜度總結

情況	時間複雜度	空間複雜度
平均	O(n log n)	O(log n)
最好	O(n log n)	O(log n)
最壞	O(n²)	O(n)

快速排序是實務中最常用的內部排序算法，理解其分區邏輯與遞歸結構，是演算法面試與系統開發的必修課。