快速排序 qsort 實現與遞歸分治邏輯詳解

算法核心：分治法

1. 選基準值
2. 分區：小於基準放左，大於放右
3. 遞歸處理左右子區

單向掃描分區代碼

void quicksort(int a[], int l, int h) {
    if (l >= h) return;
    
    int i = l, j = h;
    int key = a[i];  // 選最左作基準
    
    while (i < j) {
        while (i < j && a[j] > key) j--;  // 從右找 ≤ key
        if (i < j) a[i++] = a[j];         // 填坑，i 右移
        while (i < j && a[i] < key) i++;  // 從左找 ≥ key
        if (i < j) a[j--] = a[i];         // 填坑，j 左移
    }
    a[i] = key;  // 基準歸位
    
    quicksort(a, l, i - 1);
    quicksort(a, i + 1, h);
}

關鍵細節解析

• 填坑法：用 key 保存基準，空出 a[i] 做第一個坑，交替從右左填坑，最終 i==j 為基準歸位點
• 邊界條件：i < j 保證不越界，遞歸終止條件 l >= h
• 基準選擇：固定選最左/最右易在有序數組退化為 O(n²)，工程上常用「三數取中」或隨機選
• 不穩定性：相等元素可能被交換順序

標準庫 qsort 對比

#include <stdlib.h>

int cmp(const void *a, const void *b) {
    return *(int*)a - *(int*)b;
}

qsort(arr, n, sizeof(int), cmp);

qsort 使用快速排序變體（通常為內省排序：快排+堆排+插排混合），保證 O(n log n) 最壞情況，支持任意類型通過比較函數。

性能特徵

優化方向

1. 小區間（< 10-20）改用插入排序
2. 三數取中選基準
3. 尾遞歸優化 / 顯式棧模擬遞歸
4. 三向切分處理大量重複鍵值

快排是「原地、分治、不穩定」排序的代表，理解其分區邏輯與遞歸結構是掌握高級排序算法的基石。