分治算法經典應用：選擇問題 (第 k 小元素) 線性時間解法與中位數中位數支點選擇策略

分治算法經典應用：選擇問題 (第 k 小元素) 線性時間解法

選擇問題：在 n 個元素中找到第 k 小的元素。排序後取 a[k-1] 需 O(n log n)，但分治策略可達到 **平均 O(n)、最壞 O(n)** (配合中位數中位數支點選擇)。

基於快速選擇的分治框架

借鑑快速排序的 partition 過程：

1. 選支點 pivot
2. 分區：left (< pivot), middle (= pivot), right (> pivot)
3. 比較 k 與 |left|, |left|+|middle|：
   • k ≤ |left| → 遞歸 left 找第 k 小
   • |left| < k ≤ |left|+|middle| → pivot 即答案
   • k > |left|+|middle| → 遞歸 right 找第 k-|left|-|middle| 小
4. 每次遞歸**只進入一個分支**，而非快排的雙分支

C++ 模板實現 (平均 O(n))

#include 
#include 

template 
T Select(std::vector &a, int k) { // k: 1-based
    if (k < 1 || k > a.size()) throw std::out_of_range("k out of bounds");
    return select(a, 0, a.size() - 1, k);
}

template 
T select(std::vector &a, int l, int r, int k) {
    if (l >= r) return a[l];
    
    int i = l, j = r + 1;
    T pivot = a[l];
    
    // Partition
    while (true) {
        do { ++i; } while (i <= r && a[i] < pivot);
        do { --j; } while (a[j] > pivot);
        if (i >= j) break;
        std::swap(a[i], a[j]);
    }
    std::swap(a[l], a[j]); // pivot 歸位 j
    
    int leftSize = j - l;
    if (leftSize + 1 == k) return pivot;
    if (leftSize + 1 < k) 
        return select(a, j + 1, r, k - leftSize - 1);
    else
        return select(a, l, j - 1, k);
}

最壞情況 O(n²) 及其根源

若每次 partition 極度不平衡 (如已有序數組選首元素為支點)，遞歸深度達 n，總比較次數 Σᵢⁿ i = O(n²)。

中位數中位數支點選擇策略 — 保證最壞 O(n)

算法步驟 (r=5 或 9)

1. 將 n 元素分成 ⌈n/r⌉ 組，每組 r 個 (最後組可能不足)
2. 組內排序 (常數時間)，取各組中位數 → 形成中位數數組 M (大小 ⌈n/r⌉)
3. **遞歸調用 Select(M, ⌈|M|/2⌉)** 找到 M 的中位數 m*，作為支點

理論保證 (定理)

• r=9, n≥90：最大分支 ≤ 7n/8
• r=5, 元素互異, n≥24：最大分支 ≤ 3n/4

遞歸式：T(n) ≤ T(⌈n/r⌉) + T(αn) + O(n) (α=7/8 或 3/4) → T(n) = O(n)。

示例演示 (r=5, n=27)

原數組: [2,6,8,1,4, 10,20,6,22,11, 9,8,4,3,7, 8,16,11,10,8, 2,14,15,1,12, 5,4]
分組中位數: [4, 11, 7, 10, 12, 4]
中位數的中位數: 7 (支點)
分區: left=[2,6,1,4,6,4,3,2,1,5,4] (11個), middle=[7], right=[8,10,20,22,11,9,8,8,16,11,10,8,14,15,12] (15個)

工程實踐建議

• 工程常用：隨機化支點 (隨機選擇或 nth_element) → 期望 O(n)，代碼極簡，工程足夠。
• 硬實時/安全關鍵：中位數中位數確定性 O(n)，但常數因子大 (組內排序、遞歸開銷)，實際運行常慢於隨機化版本。
• C++ STL：std::nth_element 實現即為 Introselect (快選 + 堆排序回退)，平均 O(n)，最壞 O(n log n)，生產級首選。

應用場景

• 中位數 (k=n/2)：薪資中位數、年齡中位數、基因表達數據去噪
• 分位數 (k=n/4, n/2, 3n/4)：人口四分位分析、異常值檢測 (IQR)
• 流式數據 Top-K：結合堆結構維護滑動窗口第 k 小

選擇問題展示了分治算法「以空間換時間、以隨機化換確定性」的精妙權衡。掌握從快速選擇到中位數中位數的演進脈絡，是理解算法設計核心哲理的絕佳窗口。