C語言實現隨機不重複序列：random_n 算法詳解（空間換時間 O(N)）

前言：從簡單到高效的演進

早先寫過一版 random_n，邏輯直觀但效率一般，僅佔用一個數組。今天分享的這個版本，引入輔助數組，以 空間換時間，將最好/最壞時間複雜度穩定在 O(N)，且函數棧銷毀時自動釋放臨時數組，工程實用性更強。

核心思想：有序池 + 隨機抽取 + 末尾覆蓋

1. 先在臨時數組 temp[0..N-1] 中填入 0, 1, ..., N-1，構建有序候選池。
2. 每輪從剩餘有效長度 count 中隨機取索引 x = rand() % count。
3. 將 temp[x] 的值寫入結果數組 a[k]。
4. 用池中最後一個有效元素 temp[count-1] 覆蓋 temp[x]，並將 count--，邏輯上「移除」已取元素。
5. 循環直到池空，結果數組即為 0~N-1 的隨機排列。

完整代碼實現

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

#define MAX_NUM 10

void random_n(int a[], int n);

int main() {
    int a[MAX_NUM] = {0};
    random_n(a, MAX_NUM);
    for (int i = 0; i < MAX_NUM; i++) {
        printf("%d\t", a[i]);
    }
    printf("\n");
    return 0;
}

void random_n(int a[], int n) {
    int temp[n];          // VLA，函數返回自動釋放
    for (int k = 0; k < n; k++) temp[k] = k;  // 初始化有序池

    srand((unsigned)time(NULL));  // 種子建議放 main，此處為演示
    int count = n;
    for (int k = 0; count > 0; k++) {
        int x = rand() % count;       // 隨機索引
        a[k] = temp[x];               // 取值
        temp[x] = temp[count - 1];    // 末尾覆蓋，O(1) 刪除
        count--;
    }
}

運行結果示例

關鍵點解析

• 時間複雜度 O(N)：單層循環，每步 O(1) 操作。
• 空間複雜度 O(N)：額外一個長度 N 的臨時數組。
• 均勻隨機：每個排列出現概率相等（費雪-耶茨洗牌算法的變體）。
• 棧上分配：利用 C99 VLA（Variable Length Array）或 alloca，無需手動 malloc/free，防洩漏。

避坑提示

• srand(time(0)) 應放在 main 且僅調用一次，放在函數內多次調用會導致同一秒內生成相同序列。
• 若 N 極大（如百萬級），棧可能溢出，建議改用 malloc 配合 free。
• 嚴格說 rand() % count 有模數偏差，高精度場景請用 random / std::uniform_int_distribution (C++) 或自定義拒絕採樣。

總結

這個 random_n 實現以極小代價換取線性時間，適合嵌入式、遊戲洗牌、測試數據生成等場景。理解「有序池 + 末尾覆蓋」技巧，可舉一反三應用於各類「無放回隨機抽樣」問題。