需要在範圍 [0, N-1] 內生成一個**均勻隨機、無重複**的整數排列。朴素做法：rand() % N 後檢查是否已存在，重複則重試。但當已選取數字接近 N 時，碰撞概率極高，導致**指數級退化**，甚至陷入「死循環」假象（實為極長期望時間）。
// 期望時間 O(N²)，N=20 時已明顯卡頓
for (i = 0; i < N; ) {
int r = rand() % N;
if (!used[r]) { arr[i++] = r; used[r] = 1; }
}核心思想：維護一個「候選池」陣列 tmp[]，初始為 [0, 1, ..., N-1]。每輪從剩餘候選中隨機抽取一個，放入結果陣列，並將候選池中該位置標記為 -1，然後**壓縮候選池**（將有效元素前移），縮小抽樣範圍。
// 簡化邏輯
tmp[i] = i; // 初始化候選池
lastSize = N;
while (total < N) {
r = rand() % (N - total); // 在有效範圍內隨機
if (tmp[r] != -1) {
result[total++] = tmp[r];
tmp[r] = -1; // 標記已用
} else {
compress(tmp, lastSize); // 將 -1 後移，有效元素前移
lastSize = N - total;
}
}缺點：
O(N)，總體 O(N²)。原理：從末尾向前遍歷，每步將當前元素與 [0, i] 範圍內隨機位置交換。單次遍歷即得均勻隨機排列，時間 O(N)、空間 O(1)，無需額外陣列。
void shuffle(int *arr, int n) {
for (int i = n - 1; i > 0; --i) {
int j = rand() % (i + 1); // 0 ~ i
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
}
// 使用示例
int main() {
srand((unsigned)time(NULL)); // 必須播種！
int N = 100;
int *arr = malloc(N * sizeof(int));
for (int i = 0; i < N; ++i) arr[i] = i; // 初始有序
shuffle(arr, N);
// arr 現為均勻隨機排列
free(arr);
return 0;
}srand(time(NULL)) 僅精確到秒。高併發/高頻調用需用 clock_gettime()、rdtsc、/dev/urandom、C++11 <random> 等高熵源。rand() % (i+1) 當 RAND_MAX 非 i+1 的倍數時，分佈微弱非均勻。嚴格場景應用拒絕採樣修正：
int rand_range(int max) { // [0, max]
int limit = RAND_MAX - (RAND_MAX % (max + 1));
int r;
do { r = rand(); } while (r >= limit);
return r % (max + 1);
}#include <random>
#include <algorithm>
#include <vector>
std::vector v(N);
std::iota(v.begin(), v.end(), 0);
std::mt19937 gen(std::random_device{}());
std::shuffle(v.begin(), v.end(), gen); // 標準庫實現了無偏 Fisher-Yates N 極大（如 1 億），無法全量存儲。可用**格子洗牌**、**保留前 K 個**（Reservoir Sampling）、或**加密級 PRF**（如 AES-CTR 作為排列函數）生成虛擬排列。| 問題 | 影響 | 修正 |
|---|---|---|
無 srand() | 每次運行結果固定 | 主程式入口調用 srand(time(NULL)) |
malloc(nFloor * sizeof(int) + 1) | 多分配 1 byte，無害但不規範 | malloc(nFloor * sizeof(int)) |
rand() % (nFloor - nTotal) | 模數偏差 + 壓縮邏輯導致分佈不均 | 改用 Fisher-Yates |
壓縮函數 MergArr 複雜 | 難維護，O(N²) | 原地交換 O(N) |
生成不重複隨機序列，**Fisher-Yates 洗牌**是教科書級標準答案：簡潔、線性時間、原地操作、理論保證均勻分佈。拒絕採樣與雙陣列壓縮法僅具教學演示價值。工程上請直接使用 std::shuffle / random_shuffle（C++17 棄用）或成熟庫，並務必正確初始化高熵隨機種子。
