快速排序完整實現：Hoare 分區、隨機化優化與 C++ 模板版

算法核心思想

分治法：選基準 → 分區 (左邊 ≤ 基準 ≤ 右邊) → 遞歸排序左右子陣列。平均 O(n log n)，最壞 O(n²) (可用隨機化避免)。

三種分區方案對比

C++ 通用模板實現 (隨機化 + Hoare)

#include <algorithm>
#include <random>
#include <iterator>

template <typename RandomIt, typename Compare = std::less<>>
void quick_sort(RandomIt first, RandomIt last, Compare cmp = {}) {
    if (first >= last) return;
    // 隨機選基準，交換到 first
    std::uniform_int_distribution<size_t> dist(0, std::distance(first, last) - 1);
    std::advance(first, dist(eng));
    std::iter_swap(first, std::next(first, dist(eng))); // 實際需先算距離
    // 為簡化，這裡用 lambda 封裝 Hoare 分區
    auto partition = [&](RandomIt l, RandomIt r) {
        auto pivot = *l;
        auto i = l, j = r;
        while (true) {
            while (cmp(*++i, pivot)) if (i == r) break;
            while (cmp(pivot, *--j)) if (j == l) break;
            if (i >= j) break;
            std::iter_swap(i, j);
        }
        std::iter_swap(l, j);
        return j;
    };
    // 遞歸 (略，實際需輔助函數處理迭代器範圍)
}

簡潔可運行版 (整數數組，隨機化 Lomuto)

#include <iostream>
#include <cstdlib>
#include <ctime>
using namespace std;

void swap(int& a, int& b) { int t=a; a=b; b=t; }

int partition_rand(int a[], int l, int r) {
    int idx = l + rand() % (r - l + 1);
    swap(a[idx], a[l]); // 基準換到首位
    int pivot = a[l];
    int i = l;
    for (int j = l+1; j <= r; ++j)
        if (a[j] <= pivot) swap(a[++i], a[j]);
    swap(a[l], a[i]);
    return i;
}

void quick_sort(int a[], int l, int r) {
    if (l < r) {
        int p = partition_rand(a, l, r);
        quick_sort(a, l, p-1);
        quick_sort(a, p+1, r);
    }
}

int main() {
    srand(time(0));
    int a[] = {5,2,9,1,5,6,3};
    int n = sizeof(a)/sizeof(a[0]);
    quick_sort(a, 0, n-1);
    for (int x : a) cout << x << ' '; // 1 2 3 5 5 6 9
}

工程落地建議

• 小區間 (如 ≤ 16) 改用插入排序，減少遞歸開銷。
• 尾遞歸優化：先遞歸較小側，大側用循環，限制棧深度 O(log n)。
• C++ 實際開發直接用 std::sort (Introsort：快排+堆排+插排)，性能更穩健。