從序列取前 K 大元素 - QuickSelect + 尾部插入排序優化

問題

無序陣列 n=10⁵，求前 K=10⁴ 大元素並輸出排序結果。直接全排序 O(n log n)，能否更快？

QuickSelect 思路

快速排序分區後，主元左側皆 ≤ 主元，右側皆 ≥ 主元。
若左側長度 L：
- L == K：左側即為前 K 大 (無序)。
- L > K：遞歸左側找前 K。
- L < K：左側全要，遞歸右側找前 K-L-1 大。
平均 O(n) 找到無序 Top-K，再對這 K 個元素排序 O(K log K)。

代碼實現 (C++)

#include 
using namespace std;

template
int partition(T a[], int l, int r) { // [l, r]
    T piv = a[(l+r)/2];
    swap(a[(l+r)/2], a[r]);
    int i = l-1, j = r;
    while (true) {
        while (a[++i] < piv);
        while (i < j && piv < a[--j]);
        if (i >= j) break;
        swap(a[i], a[j]);
    }
    swap(a[i], a[r]);
    return i;
}

template
void quickSelect(T a[], int l, int r, int k) { // 找前 k 大 (k>=1)
    if (l >= r) return;
    int p = partition(a, l, r);
    int leftSize = p - l;
    if (leftSize == k-1) return;
    if (leftSize > k-1) quickSelect(a, l, p-1, k);
    else quickSelect(a, p+1, r, k - leftSize - 1);
}

template
void insertionSort(T a[], int n) {
    for (int i=1;i=0 && a[j]>t) a[j+1]=a[j--];
        a[j+1]=t;
    }
}

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    const int N=100000, K=10000;
    vector a(N);
    for(int& x:a) cin>>x; // 或從檔案讀取
    quickSelect(a.data(), 0, N-1, K);
    insertionSort(a.data(), K);
    for(int i=0;i

實測數據 (隨機 10⁵ 整數)

方法
耗時

std::sort 全排序 + 取前 K
1.05 s
QuickSelect + InsertionSort(K)
0.98 s


優化約 7%，隨機數據下優勢不明顯，但在近乎有序或K ≪ n時效果更顯著。

工程建議

生產環境直接用 std::nth_element (Introselect 保證 O(n) 最壞) + std::sort(begin, begin+K)，碼少且穩健。
若 K 極小 (如 K≤100)，維護大小 K 的最小堆 O(n log K) 更簡單、常數更小。


總結
QuickSelect 是「第 K 大 / 前 K 大」理論最優解，理解其分區遞歸邏輯有助於掌握選擇算法核心。實務上優先用標準庫 nth_element 或堆，除非有極致性能需求需手寫優化。