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

算法原理

快速選擇基於快速排序的 partition：每次划分後，枢軸左側元素皆 ≤ 枢軸，右側 ≥ 枢軸。若枢軸索引 == k-1，即為第 k 小；否則遞歸處理左或右子陣列。平均 O(n)，最壞 O(n²)。

修正後完整代碼（含 partition）

#include <stdio.h>
#include <stdlib.h>

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

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 quickSelect(int a[], int low, int high, int k) {
    if (low == high) return a[low];
    int pos = partition(a, low, high);
    int leftCount = pos - low + 1;
    if (leftCount == k) return a[pos];
    else if (leftCount > k) return quickSelect(a, low, pos-1, k);
    else return quickSelect(a, pos+1, high, k - leftCount);
}

int main() {
    int n, k;
    printf("陣列大小: "); scanf("%d", &n);
    int *a = malloc(n * sizeof(int));
    for (int i=0; i<n; i++) { printf("第%d個: ", i+1); scanf("%d", &a[i]); }
    printf("查找第 k 小 (1-based): "); scanf("%d", &k);
    if (k > 0 && k <= n)
        printf("第 %d 小元素: %d\n", k, quickSelect(a, 0, n-1, k));
    else
        printf("k 超出範圍\n");
    free(a);
    return 0;
}

關鍵點解析

• partition 就地重排，回傳枢軸最終位置。
• leftCount 計算左側含枢軸的元素數，決定遞歸方向與新 k 值。
• 原始碼第二版 partition 邏輯錯誤（do i++; while(array[i] < array[p]) 缺少邊界檢查），此處已修正。
• 隨機化選擇枢軸（swap(a[low], a[rand()%(high-low+1)+low])）可避免最壞情況。

複雜度分析

• 平均：O(n) —— 每次約淘汰一半元素。
• 最壞：O(n²) —— 每次僅淘汰枢軸（已排序陣列）。
• 空間：O(log n) 遞歸深度（平均），最壞 O(n)。

工程建議

1. 生產環境用 nth_element (C++) 或 stdlib 的 qsort 排序後直接取 a[k-1]（O(n log n) 但常數小、無最壞情況）。
2. 若必須 O(n)，使用中位數的中位數（BFPRT）算法保證最壞線性，但常數極大，實際較少用。
3. 注意 k 為 1-based，內部邏輯統一處理。

快速選擇是分治策略在選擇問題上的經典應用，理解其划分邏輯與遞歸縮減過程，對掌握快速排序、中位數查找等算法大有裨益。