C 語言演算法實作：分治法之快速排序完整指南

前言

快速排序是分治法最經典的應用之一，平均時間複雜度 O(n log n)、原地排序、緩存友好，是實務中最常用的排序演算法。本文深入解析快速排序原理、分區策略、優化技巧與 C++ 實作細節。

核心思想：分治三步曲

1. 分：選擇一個基準元素，將陣列分為「小於基準」「等於基準」「大於基準」三段
2. 治：遞迴排序左段與右段
3. 合：無需合併，因為分區過程已將元素移至正確區域

分區演算法

Hoare 分區法（原版）

雙指針從兩端向中間掃描，交換順序錯誤的元素：

template <class T>
void quickSort(T a[], int l, int r) {
    if (l >= r) return;
    
    int i = l, j = r + 1;
    T pivot = a[l];  // 選最左元素為基準
    
    while (true) {
        do { i++; } while (a[i] < pivot);   // 找 ≥ pivot
        do { j--; } while (a[j] > pivot);   // 找 ≤ pivot
        if (i >= j) break;
        swap(a[i], a[j]);
    }
    
    swap(a[l], a[j]);  // 基準歸位
    quickSort(a, l, j-1);
    quickSort(a, j+1, r);
}

Lomuto 分區法（教學常用）

單指針維護「小於基準區域」邊界：

int partition(T a[], int l, int r) {
    T pivot = a[r];  // 選最右元素
    int i = l - 1;
    for (int j = l; j < r; j++) {
        if (a[j] <= pivot)
            swap(a[++i], a[j]);
    }
    swap(a[i+1], a[r]);
    return i + 1;
}

比較： Hoare 交換次數較少、效能較好；Lomuto 邏輯簡單但退化情況較差。

效能分析

最佳情況：O(n log n)

每次分區完美平分，遞迴深度 log₂ n，每層處理 n 個元素。

最壞情況：O(n²)

每次分區極度不平衡（如已排序陣列選首/尾元素為基準），遞迴深度 n。

平均情況：O(n log n)

數學期望證明：T(n) = (2/n) Σ T(k) + cn，解得 T(n) ≈ 2n ln n。

空間複雜度

• 遞迴棧：最佳 O(log n)、最壞 O(n)
• 可透過「尾遞迴消除」+「先處理較小分區」將最壞空間降為 O(log n)

關鍵優化技巧

1. 三數取中法選基準

從 a[l]、a[(l+r)/2]、a[r] 中選中位數作為基準，大幅減少最壞情況發生機率：

T medianOfThree(T a[], int l, int r) {
    int mid = (l + r) / 2;
    if (a[l] > a[mid]) swap(a[l], a[mid]);
    if (a[l] > a[r]) swap(a[l], a[r]);
    if (a[mid] > a[r]) swap(a[mid], a[r]);
    swap(a[mid], a[l]);  // 基準移至 a[l]
    return a[l];
}

2. 小陣列改用插入排序

當陣列長度 ≤ 閾值（通常 10~20）時，插入排序常數因子更小：

const int INSERTION_SORT_THRESHOLD = 15;

void quickSort(T a[], int l, int r) {
    if (r - l <= INSERTION_SORT_THRESHOLD) {
        insertionSort(a, l, r);
        return;
    }
    // ... 正常快排邏輯
}

3. 三向切分：處理大量重複元素

荷蘭國旗問題思想，將陣列分為 < pivot、= pivot、> pivot 三段：

void quickSort3Way(T a[], int l, int r) {
    if (l >= r) return;
    T pivot = a[l];
    int lt = l, gt = r, i = l;
    
    while (i <= gt) {
        if (a[i] < pivot) swap(a[lt++], a[i++]);
        else if (a[i] > pivot) swap(a[i], a[gt--]);
        else i++;
    }
    
    quickSort3Way(a, l, lt-1);
    quickSort3Way(a, gt+1, r);
}

4. 尾遞迴消除 + 迭代實作

void quickSortIterative(T a[], int l, int r) {
    std::stack<std::pair<int,int>> st;
    st.push({l, r});
    
    while (!st.empty()) {
        auto [l, r] = st.top(); st.pop();
        while (l < r) {
            int p = partition(a, l, r);
            // 先處理較小分區，較大分區入棧
            if (p - l < r - p) {
                if (p + 1 < r) st.push({p+1, r});
                r = p - 1;
            } else {
                if (l < p - 1) st.push({l, p-1});
                l = p + 1;
            }
        }
    }
}

隨機化快速排序

隨機選擇基準，將最壞情況機率降至極低（期望 O(n log n)）：

int randomPartition(T a[], int l, int r) {
    int randIdx = l + rand() % (r - l + 1);
    swap(a[randIdx], a[r]);
    return partition(a, l, r);
}

實戰測試數據（參考）

常見錯誤與除錯

• 無限遞迴：分區點未正確縮小範圍（如 quickSort(a, l, j) 應為 j-1）
• 陣列越界：指針移動條件順序錯誤，應先移動再比較
• 基準值丟失：交換基準前未保存數值
• 棧溢位：未優化尾遞迴，極端情況棧深度 O(n)

標準庫替代方案

生產環境建議直接使用 std::sort（Introsort：快排+堆排+插入排混合），保證 O(n log n) 最壞情況：

#include <algorithm>
#include <vector>

std::vector<int> v = {5, 2, 8, 1, 9};
std::sort(v.begin(), v.end());  // 平均 O(n log n)，最壞 O(n log n)

快速排序是分治法的集大成者，理解其分區邏輯、遞迴結構與優化策略，不僅能實作高效排序，更能培養演算法設計的核心思維。掌握三向切分、隨機化基準、小陣列切換等技巧，可構建生產級的排序常式。