C 語言第 K 小元素：選擇演算法與邊界條件修正

原始碼嘗試用「每次找最小值並移除」的方式求第 K 小，但存在嚴重缺陷：

• n[q] = n[q+1] 在 q 為最後一個元素時會**陣列越界**。
• 未處理重複值，移除邏輯會導致資料遺失。
• 時間複雜度 O(K·N)，K 接近 N 時退化為 O(N²)。

正確做法：QuickSelect (Hoare 選擇算法)

int partition(int a[], int l, int r) {
    int pivot = a[r], 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;
}

int quickSelect(int a[], int l, int r, int k) { // k 從 1 開始
    if (l == r) return a[l];
    int p = partition(a, l, r);
    int rank = p - l + 1;
    if (k == rank) return a[p];
    else if (k < rank) return quickSelect(a, l, p-1, k);
    else return quickSelect(a, p+1, r, k-rank);
}

替代方案

• 小資料量 (N ≤ 1e5) 直接 qsort 後取 a[k-1]，簡單可靠。
• C++ 可用 nth_element 平均 O(N)。

核心觀念：避免手動移動陣列元素，改用分治法在原地分區，即能高效求第 K 小並天然避免越界。