C 語言生成 N 個不重複隨機數（續）：O(N) 洗牌法，以空間換時間

核心思想：Fisher-Yates 洗牌變體

1. 建立輔助陣列 temp[0..N-1] = {0, 1, ..., N-1}（有序池）。
2. 維護 count 表示池中剩餘有效元素數（初始 N）。
3. 每輪從 [0, count-1] 隨機選索引 x，取出 temp[x] 放入結果陣列。
4. 將池尾元素 temp[count-1] 移至 temp[x] 填補空位，count--。
5. 重複直到 count == 0。

每輪必產出一個不重複數，零重試，嚴格 O(N)。

完整程式碼

#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], i = 0;
    while (i < MAX_NUM) a[i++] = -1;
    random_n(a, MAX_NUM);
    for (i = 0; i < MAX_NUM; ++i) printf("%d\t", a[i]);
    printf("\n");
    return 0;
}

void random_n(int a[], int n) {
    int temp[MAX_NUM];   // 變長陣列 (C99) 或動態分配
    for (int k = 0; k < n; ++k) temp[k] = k;

    srand((unsigned)time(NULL));
    int count = n, k = 0, x;
    while (count > 0) {
        x = rand() % count;
        a[k++] = temp[x];
        temp[x] = temp[count - 1];  // 尾元素填補
        --count;
    }
}

執行過程圖解（N=5）

初始池：[0][1][2][3][4]  count=5
隨機 x=2 → 取 2 → 結果[2]  池變 [0][1][4][3]  count=4
隨機 x=0 → 取 0 → 結果[2,0] 池變 [3][1][4]    count=3
隨機 x=2 → 取 4 → 結果[2,0,4] 池變 [3][1]      count=2
隨機 x=1 → 取 1 → 結果[2,0,4,1] 池變 [3]       count=1
隨機 x=0 → 取 3 → 結果[2,0,4,1,3] 池空        count=0

複雜度對比

工程落地建議

• 大 N：改用動態分配 int* temp = malloc(n * sizeof(int))，用完 free。
• 隨機源：rand() 品質有限，生產環境建議 arc4random、random()、C++11 std::mt19937。
• 模數偏差：rand() % count 仍有微小偏差，嚴格均勻需用拒絕採樣。
• 執行緒安全：rand/srand 非執行緒安全，多執行緒用 rand_r 或 C++11 引擎。

思考延伸

此演算法本質是隨機排列（Random Permutation）。若只需前 K 個不重複數（K < N），可在 k == K 時提前結束，進一步節省時間。