快速排序 C++ 實現：多種樞軸選擇與優化策略

基礎分區

以最後一個元素為樞軸，雙指針 `fast`/`slow` 掃描，將 ≤ 樞軸的元素交換到前部。

template
int partition1(vector& a, int l, int r) {
    T key = a[r];
    int slow = l;
    for (int fast = l; fast < r; ++fast)
        if (a[fast] <= key) swap(a[slow++], a[fast]);
    swap(a[slow], a[r]);
    return slow;
}

三數取中樞軸

取 `a[l]`、`a[mid]`、`a[r]` 中位數作為樞軸，避免有序數組退化。

template
T median3(T x, T y, T z) {
    return max(min(x,y), min(max(x,y), z));
}
template
int partition2(vector& a, int l, int r) {
    int m = (l + r) >> 1;
    T key = median3(a[l], a[m], a[r]);
    // 將 key 換到 a[r]
    if (key == a[l]) swap(a[l], a[r]);
    else if (key == a[m]) swap(a[m], a[r]);
    // 單邊掃描交換
    int i = l, j = r - 1;
    while (true) {
        while (a[++i] < key);
        while (a[--j] > key);
        if (i >= j) break;
        swap(a[i], a[j]);
    }
    swap(a[i], a[r]);
    return i;
}

隨機樞軸

隨機選擇索引，期望 O(n log n)。

template
int partition3(vector& a, int l, int r) {
    int idx = l + rand() % (r - l + 1);
    swap(a[idx], a[r]);
    T key = a[r];
    int i = l, j = r - 1;
    while (true) {
        while (a[++i] < key);
        while (a[--j] > key);
        if (i >= j) break;
        swap(a[i], a[j]);
    }
    swap(a[i], a[r]);
    return i;
}

避免不必要的交換（單向掃描）

template
int partition4(vector& a, int l, int r) {
    int idx = l + rand() % (r - l + 1);
    swap(a[idx], a[r]);
    T key = a[r];
    int i = l;
    for (int j = l; j < r; ++j)
        if (a[j] < key) swap(a[i++], a[j]);
    swap(a[i], a[r]);
    return i;
}

尾遞歸優化 / 迭代版

手動模擬棧，先處理較小分區，限制棧深度 O(log n)。

template
void quickSort(vector& a) {
    vector> stk;
    stk.emplace_back(0, (int)a.size()-1);
    while (!stk.empty()) {
        auto [l, r] = stk.back(); stk.pop_back();
        if (l >= r) continue;
        int p = partition4(a, l, r);
        // 先壓入較大分區，再處理較小分區（循環）
        if (p - l < r - p) {
            stk.emplace_back(p+1, r);
            stk.emplace_back(l, p-1);
        } else {
            stk.emplace_back(l, p-1);
            stk.emplace_back(p+1, r);
        }
    }
}

小區間插入排序優化

當區間長度 ≤ 16 時改用插入排序，減少遞歸開銷。

const int INSERT_THRESHOLD = 16;
template
void insertionSort(vector& a, int l, int r) {
    for (int i = l+1; i <= r; ++i) {
        T tmp = a[i];
        int j = i;
        while (j > l && a[j-1] > tmp) a[j] = a[--j];
        a[j] = tmp;
    }
}
// 在 quickSort 遞歸入口加入：
if (r - l + 1 <= INSERT_THRESHOLD) { insertionSort(a, l, r); return; }

總結

• 樞軸選擇：三數取中或隨機，防退化。
• 分區方案：單向掃描（`partition4`）交換次數最少。
• 遞歸優化：尾遞歸消除 + 手動棧 + 小區間插入排序。
• C++ 標準庫 `std::sort` 通常採用 Introsort（快排 + 堆排兜底），性能更強。