C# 實作費雪-耶茨演算法：高效打亂 1~20 數字陣列

背景：為何需要「真正隨機」的洗牌演算法？

早期嘗試採用「隨機抽取並移除」方式，但易產生邊界偏差（例如數字 2 後總跟著 1）。改用 費雪-耶茨演算法，可在 O(n) 時間內完成原地打亂，且機率分布均勻，是洗牌、抽獎、測試資料生成的標準作法。

核心程式碼

using System;

public class RandomShuffler
{
    private readonly Random _random = new Random();

    /// 

    /// 將傳入的整數陣列原地隨機打亂
    /// 
    public void Shuffle(int[] array)
    {
        if (array == null || array.Length <= 1) return;

        for (int i = array.Length - 1; i > 0; i--)
        {
            int randomIndex = _random.Next(0, i + 1); // 0 ~ i 含邊界
            // 交換 array[i] 與 array[randomIndex]
            int temp = array[i];
            array[i] = array[randomIndex];
            array[randomIndex] = temp;
        }
    }
}

使用範例

var numbers = new int[20];
for (int i = 0; i < 20; i++) numbers[i] = i + 1; // 1~20

var shuffler = new RandomShuffler();
shuffler.Shuffle(numbers);

// 輸出結果
Console.WriteLine(string.Join(", ", numbers));

演算法優勢

• 時間複雜度 O(n)：單一迴圈完成，無額外記憶體配置。
• 均勻分布：每個排列組合出現機率相等（1/n!）。
• 原地操作：不需額外陣列，記憶體效率高。

常見錯誤避坑指南

1. 隨機索引範圍錯誤：_random.Next(0, i) 應為 _random.Next(0, i + 1)，否則最後一個元素永不被交換。
2. 重複建立 Random 實例：短時間內多次 new Random() 會因種子相同產生相同序列，請共用單一實例。
3. 執行緒安全：Random 非執行緒安全，多執行緒環境請改用 ThreadLocal<Random> 或 lock 保護。

擴充應用：泛型版本支援任意型別

public static class ShuffleExtensions
{
    private static readonly Random _random = new Random();

    public static void Shuffle<T>(this T[] array)
    {
        if (array == null || array.Length <= 1) return;
        for (int i = array.Length - 1; i > 0; i--)
        {
            int j = _random.Next(0, i + 1);
            (array[i], array[j]) = (array[j], array[i]); // C# 7+ tuple 交換
        }
    }
}

如此即可對 string[]、CustomObject[] 等任意陣列呼叫 array.Shuffle()。