算法題：求無序數組中最小的 k 個數（快速選擇 / QuickSelect）

問題描述

輸入 n 個整數，找出其中最小的 k 個數。要求時間複雜度優於 O(n log n)。

QuickSelect 思路

利用快速排序的 Partition 過程：每次劃分後，基準元素位於最終排序位置 index。若 index == k-1，前 k 個即為答案；若 index > k-1，遞歸左半部；否則遞歸右半部。平均 O(n)，最壞 O(n²)，引入隨機基準可期望線性時間。

核心代碼

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

int RandomInRange(int min, int max) {
    return rand() % (max - min + 1) + min;
}

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

int Partition(int data[], int len, int start, int end) {
    if (!data || len <= 0 || start < 0 || end >= len) return -1;
    int idx = RandomInRange(start, end);
    Swap(&data[idx], &data[end]);
    int small = start - 1;
    for (idx = start; idx < end; ++idx) {
        if (data[idx] < data[end]) {
            ++small;
            if (small != idx) Swap(&data[small], &data[idx]);
        }
    }
    ++small;
    Swap(&data[small], &data[end]);
    return small;
}

void GetLeastNumbers(int* input, int n, int* output, int k) {
    if (!input || n <= 0 || !output || k <= 0 || k > n) return;
    int start = 0, end = n - 1;
    int idx = Partition(input, n, start, end);
    while (idx != k - 1) {
        if (idx > k - 1) {
            end = idx - 1;
        } else {
            start = idx + 1;
        }
        idx = Partition(input, n, start, end);
    }
    for (int i = 0; i < k; ++i) output[i] = input[i];
}

int main(void) {
    int data[] = {4, 5, 1, 6, 2, 7, 3, 8};
    int out[4];
    GetLeastNumbers(data, 8, out, 4);
    for (int i = 0; i < 4; ++i) printf("%d ", out[i]); // 1 2 3 4
    return 0;
}

輸出

1 2 3 4