Fisher-Yates 洗牌演算法：為什麼隨機排序不能只用亂數？

你按下「隨機排序」，結果真的夠隨機嗎？大多數人以為，只要呼叫亂數函式就能得到公平的隨機排列。但事實上，錯誤的實作方式會讓某些排列出現的機率遠高於其他排列，造成隱性偏差。本文從原理出發，解析正確的隨機洗牌演算法——Fisher-Yates Shuffle。

1. 什麼是「公平的隨機排列」？

假設有 3 個元素 [A, B, C]，全部可能的排列有 3! = 6 種：

ABC  ACB  BAC  BCA  CAB  CBA

「公平的隨機排列」意味著每一種排列被選中的機率都是 1/6 ≈ 16.67%，不偏向任何特定順序。如果某種實作讓 ABC 出現機率變成 20%，其他排列只有 16%，這就是有偏差的隨機——即使表面上「看起來很亂」。

2. 直覺做法的陷阱：Sort + Math.random()

許多開發者寫過這樣的程式碼（以 JavaScript 為例）：

// 常見但有偏差的做法
array.sort(() => Math.random() - 0.5);

這個做法看起來合理，但實際上有嚴重的偏差問題。原因在於：

排序演算法假設比較結果是一致的：快速排序、歸併排序等演算法在排序過程中會多次比較同兩個元素，預期「A > B」的結果在每次比較時應一致。但隨機比較函式每次呼叫都可能翻轉，導致演算法走入非預期路徑。
數學上無法保證均勻分佈：比較排序的時間複雜度是 O(n log n)，代表它只做了 n log n 次比較。對於 n 個元素，可能的排列有 n! 種。當 n! 遠大於比較次數能區分的狀態時，某些排列必然被「合併」，出現機率不均。

統計驗證

對 [1,2,3] 用 sort+random 跑 100 萬次，你會發現某些排列出現約 20%，而非均等的 16.67%。偏差雖然不大，但在需要公平性的抽籤場合不可接受。

3. Fisher-Yates 演算法的原理

Fisher-Yates Shuffle（現代版本又稱 Knuth Shuffle）由 Ronald Fisher 和 Frank Yates 於 1938 年提出，Donald Knuth 在《電腦程式設計藝術》中推廣了其現代變體。

演算法步驟（以 n 個元素的陣列為例）：

從最後一個元素（索引 n-1）開始，向前遍歷到索引 1。
對於當前索引 i，在 [0, i]（含兩端）範圍內隨機選一個索引 j。
交換 array[i] 與 array[j]。
繼續處理索引 i-1，直到 i = 1 為止。

// Fisher-Yates Shuffle（JavaScript 正確實作）
function shuffle(array) {
    const a = [...array]; // 不修改原陣列
    for (let i = a.length - 1; i > 0; i--) {
        const j = Math.floor(Math.random() * (i + 1));
        [a[i], a[j]] = [a[j], a[i]]; // 交換
    }
    return a;
}

4. 為什麼 Fisher-Yates 能保證均勻分佈？

以 3 個元素 [A, B, C] 為例，逐步分析機率：

步驟	操作	機率
i=2	從 [0,1,2] 選 j，決定第 3 個位置的元素	各 1/3
i=1	從 [0,1] 選 j，決定第 2 個位置的元素	各 1/2
i=0	第 1 個位置固定為剩餘元素	1

每種完整排列的機率：

P(任意特定排列) = 1/3 × 1/2 × 1 = 1/6

數學上完全均勻！對於 n 個元素，每種排列出現機率精確為 1/n!，前提是亂數函式本身是均勻分佈的。

5. 正確亂數的重要性

Fisher-Yates 演算法的公平性建立在「亂數函式均勻分佈」的假設上。不同環境的亂數品質差異很大：

環境	函式	適用場合
JavaScript（瀏覽器）	`Math.random()`	一般抽籤、遊戲（非密碼學用途）
JavaScript（需高品質）	`crypto.getRandomValues()`	安全抽籤、彩券系統
Python	`random.shuffle()`	一般用途（已內建 Fisher-Yates）
Python（安全）	`secrets.SystemRandom().shuffle()`	需要密碼學強度的場合
PHP	`shuffle()`	一般用途

對於班級分組、活動抽籤等日常用途，Math.random() 的品質完全足夠。若是需要法律效力的抽籤（如公開抽號碼牌），則應使用加密安全的亂數來源。

6. 分組的實作：從洗牌到分配

「隨機分組」其實是「隨機排序 + 均勻分配」兩個步驟的組合：

function randomGroup(names, groupCount) {
    const shuffled = shuffle(names);      // 第一步：Fisher-Yates 洗牌
    const groups = Array.from({ length: groupCount }, () => []);
    shuffled.forEach((name, i) => {
        groups[i % groupCount].push(name); // 第二步：輪流分配到各組
    });
    return groups;
}

輪流分配（i % groupCount）確保各組人數差距最多 1 人。若 10 人分 3 組，結果會是 4、3、3 人，而非 4、4、2 這種更不均勻的情況。

7. 常見誤區總結

誤區	問題	正確做法
array.sort(() => Math.random() - 0.5)	統計上有偏差	使用 Fisher-Yates
每次給元素一個隨機數再排序	理論上正確但效率低	直接用 Fisher-Yates（O(n) vs O(n log n)）
只選前 n 個隨機元素	不是完整洗牌	Fisher-Yates 的前 n 步即為「無放回抽樣」
在同一位置「原地隨機交換」多次	某些位置被交換機率更高	每個位置只交換一次

延伸應用

Fisher-Yates 的前 k 步就是「從 n 個元素中無放回隨機抽取 k 個」的最佳演算法，時間複雜度 O(k)，不需要對整個陣列完整洗牌。在抽獎、隨機抽題等場合非常有用。

8. 小結

隨機排序看似簡單，但「看起來很亂」和「統計上均勻」是兩回事。Fisher-Yates 演算法以 O(n) 的時間複雜度、精確的數學保證，成為業界標準的洗牌做法。無論是班級分組、活動抽籤還是遊戲發牌，使用正確的演算法才能確保每個人機會均等。

想直接體驗隨機分組效果，可以使用本站的名單分組工具，輸入名單後即可隨機排序或分組，結果可直接複製使用。