C# 洗牌演算法實作：Fisher-Yates Shuffle 與三種隨機數策略比較

前言

陣列/列表隨機重排（Shuffle）是常見需求：撲克牌發牌、題目隨機、測試資料打散。本文實作經典 Fisher-Yates (Knuth) Shuffle，並比較三種隨機數來源對結果隨機性的影響，附帶 C++ STL 標準實作參考。

演算法核心邏輯

從陣列尾端向前遍歷，每步在「當前索引 ≤ i 的範圍」隨機選一個位置交換：

for (int i = list.Count - 1; i > 0; i--)
{
    int j = random.Next(0, i + 1); // [0, i]
    (list[i], list[j]) = (list[j], list[i]); // 交換
}

時間複雜度 O(n)、空間 O(1)、無偏差（每個排列機率均等 1/n!）。

三種隨機數策略實作

1. System.Random（預設種子 = 環境刻度）

public static List<int> Shuffle(int size)
{
    var list = Enumerable.Range(0, size).ToList();
    var rand = new Random(); // 預種子 Environment.TickCount
    for (int i = list.Count - 1; i > 0; i--)
    {
        int j = rand.Next(i + 1);
        (list[i], list[j]) = (list[j], list[i]);
    }
    return list;
}

缺點：短時間內連續實例化 `new Random()` 會取得相同種子，導致相同序列。解決：共用單一 `Random` 實例（需執行緒安全）或改用下列策略。

2. Random + RNGCryptoServiceProvider 種子

public static List<int> ShuffleEx(int size)
{
    var list = Enumerable.Range(0, size).ToList();
    // 使用加密強度雜湊碼作種子
    var rand = new Random(new RNGCryptoServiceProvider().GetHashCode());
    for (int i = list.Count - 1; i > 0; i--)
    {
        int j = rand.Next(i + 1);
        (list[i], list[j]) = (list[j], list[i]);
    }
    return list;
}

種子熵較高，但 `Random` 本身仍為偽隨機演算法，長序列有週期性。

3. 直接使用 RNGCryptoServiceProvider（密碼學強度）

public static List<int> ShufflePro(int size)
{
    var list = Enumerable.Range(0, size).ToList();
    var rng = new RNGCryptoServiceProvider();
    var bytes = new byte[4];

    for (int i = list.Count - 1; i > 0; i--)
    {
        rng.GetNonZeroBytes(bytes); // 取得 4 位元組非零隨機數
        // 組合成 32 位元整數（大端序）
        int randomSeed = (bytes[0] << 24) | (bytes[1] << 16) | (bytes[2] << 8) | bytes[3];
        int j = Math.Abs(randomSeed % (i + 1)); // 映射到 [0, i]
        (list[i], list[j]) = (list[j], list[i]);
    }
    return list;
}

優點：真隨機來源，適合密碼學、博弈、安全敏感場景。缺點：效能較 `Random` 低約 10-50 倍。

效能與適用場景對比

.NET 6+ 現代化寫法

// Random.Shared (執行緒安全單例) - .NET 6+
public static void ShuffleModern<T>(IList<T> list)
{
    for (int i = list.Count - 1; i > 0; i--)
    {
        int j = Random.Shared.Next(i + 1);
        (list[i], list[j]) = (list[j], list[i]);
    }
}

// RandomNumberGenerator (取代 RNGCryptoServiceProvider) - .NET Core 3.0+
public static void ShuffleSecure<T>(IList<T> list)
{
    using var rng = RandomNumberGenerator.Create();
    var bytes = new byte[4];
    for (int i = list.Count - 1; i > 0; i--)
    {
        rng.GetNonZeroBytes(bytes);
        int r = (bytes[0] << 24) | (bytes[1] << 16) | (bytes[2] << 8) | bytes[3];
        int j = Math.Abs(r % (i + 1));
        (list[i], list[j]) = (list[j], list[i]);
    }
}

C++ STL 標準實作參考 (VC8)

template <class _RanIt, class _Diff> inline
void _Random_shuffle(_RanIt _First, _RanIt _Last, _Diff *)
{
    const int _RANDOM_BITS = 15; // rand() 至少 15 bits
    const int _RANDOM_MAX = (1U << _RANDOM_BITS) - 1;
    _RanIt _Next = _First;
    for (unsigned long _Index = 2; _Next != _Last; ++_Next, ++_Index)
    {
        unsigned long _Rm = _RANDOM_MAX;
        unsigned long _Rn = ::rand() & _RANDOM_MAX;
        for (; _Rm < _Index && _Rm != ~0UL; _Rm = _Rm << _RANDOM_BITS | _RANDOM_MAX)
            _Rn = _Rn << _RANDOM_BITS | (::rand() & _RANDOM_MAX); // 擴大隨機範圍
        std::iter_swap(_Next, _First + _Diff(_Rn % _Index));
    }
}

STL 為了應對 `rand()` 位數不足，採用多次疊加擴大隨機範圍，再取模。

常見錯誤與避坑

1. new Random() 在迴圈內：種子相同 → 完全相同序列。解決：提升為靜態/共用實例或用 `Random.Shared`。
2. rand.Next(0, list.Count) 而非 rand.Next(i+1)：導致分布偏差（前段元素移動機率過高）。
3. 直接用 Guid.NewGuid() 排序：`list.OrderBy(x => Guid.NewGuid())` 雖簡潔但 O(n log n)、記憶體開銷大、非原地演算法。
4. 模運算偏差：`random % n` 當隨機數範圍非 n 倍數時，低位數機率略高。嚴格場景需用「拒絕採樣」。

總結

• 一般應用：**`Random.Shared` + Fisher-Yates** 最佳平衡。
• 安全敏感：**`RandomNumberGenerator` + Fisher-Yates**。
• 切勿自創演算法，標準 Fisher-Yates 經數學證明無偏差，且極簡好維護。