純 C 語言分治法查找第 K 小元素：快速選擇算法實現

在無序數組中查找第 K 小元素，排序法 O(N log N)，快速選擇算法（QuickSelect）平均 O(N)、最壞 O(N²)。本文給出基於快速排序 partition 邏輯的遞歸實現，並提供迭代優化版本。

核心思想：Partition + 遞歸

1. 選取基準（如首元素），partition 將數組劃分為 [< pivot] [pivot] [> pivot]。
2. 設基準最終位置為 pos，左側元素個數 = pos - low。
   • 若 K-1 == pos → 直接返回 a[pos]。
   • 若 K-1 < pos → 在左半部遞歸查找第 K 小。
   • 若 K-1 > pos → 在右半部遞歸查找第 K - (pos - low + 1) 小。

遞歸實現（修正版）

#include 
#include 

int partition(int a[], int low, int high) {
    int pivot = a[low];
    int i = low, j = high;
    while (i < j) {
        while (i < j && a[j] >= pivot) j--;
        if (i < j) a[i++] = a[j];
        while (i < j && a[i] <= pivot) i++;
        if (i < j) a[j--] = a[i];
    }
    a[i] = pivot;
    return i;
}

int quick_select(int a[], int low, int high, int k) { // k 從 1 開始
    if (low == high) return a[low];
    int pos = partition(a, low, high);
    int left_count = pos - low + 1; // 基準及左側元素數
    if (k == left_count) return a[pos];
    else if (k < left_count) return quick_select(a, low, pos-1, k);
    else return quick_select(a, pos+1, high, k - left_count);
}

int main() {
    int a[10];
    printf("輸入 10 個整數:\n");
    for (int i = 0; i < 10; i++) scanf("%d", &a[i]);
    int k; printf("查找第 K 小 (1-10): "); scanf("%d", &k);
    if (k < 1 || k > 10) { printf("K 越界\n"); return 1; }
    int ans = quick_select(a, 0, 9, k);
    printf("第 %d 小元素 = %d\n", k, ans);
    return 0;
}

迭代版本（消除遞歸棧）

int quick_select_iter(int a[], int n, int k) {
    int low = 0, high = n - 1;
    while (low <= high) {
        int pos = partition(a, low, high);
        int left_count = pos - low + 1;
        if (k == left_count) return a[pos];
        else if (k < left_count) high = pos - 1;
        else { k -= left_count; low = pos + 1; }
    }
    return -1; // 不應到達
}

關鍵優化：隨機化基準

固定選首元素在有序/近有序數組退化為 O(N²)。隨機選取基準 可保證期望 O(N)：

int rand_partition(int a[], int low, int high) {
    int r = low + rand() % (high - low + 1);
    swap(&a[low], &a[r]);
    return partition(a, low, high);
}

複雜度對比

總結

第 K 小元素查找是分治算法的經典應用。**工程上推薦隨機化 QuickSelect 迭代版**：平均線性時間、常數空間、代碼簡潔。理解 partition 如何將問題規模指數級縮減，是掌握分治精髓的關鍵。