C# List 隨機打亂 (Shuffle) 高效能單行實作

核心演算法：Fisher-Yates (Knuth Shuffle)

標準 O(n) 原地打亂：從尾端往前，每次隨機選一個未處理位置交換。

擴充方法實作 (標準、可測試、可複用)

using System;
using System.Collections.Generic;

public static class ListExtensions
{
    private static readonly Random _rng = Random.Shared; // .NET 6+ 共用執行緒安全實例

    /// 

    /// 原地打亂 (Fisher-Yates)
    /// 
    public static void Shuffle(this IList list)
    {
        if (list == null) throw new ArgumentNullException(nameof(list));
        for (int i = list.Count - 1; i > 0; i--)
        {
            int j = _rng.Next(i + 1); // 0 ~ i
            (list[i], list[j]) = (list[j], list[i]); // C# 7+ tuple swap
        }
    }

    /// 

    /// 回傳新打亂清單 (不修改原清單)
    /// 
    public static List ToShuffledList(this IEnumerable source)
    {
        var list = new List(source);
        list.Shuffle();
        return list;
    }
}

使用範例

var numbers = new List { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
numbers.Shuffle();
Console.WriteLine(string.Join(", ", numbers)); // 每次順序不同

// LINQ 風格 (不修改原序列)
var shuffled = Enumerable.Range(1, 10).ToShuffledList();

為什麼不推薦 `Insert(Random, item)`？

// 文中提到的做法
var newList = new List();
foreach (var item in source)
    newList.Insert(rng.Next(newList.Count), item); // O(n^2)！

效能災難：`List.Insert` 需搬移後續所有元素，平均 O(n)，總複雜度 **O(n²)**。
Fisher-Yates 僅交換參考，**O(n)**，快 100 倍以上 (n=10,000 時)。

執行緒安全與可重現性

• 共用 Random：`Random.Shared` (.NET 6+) 或 `static readonly ThreadLocal` 避免種子碰撞。
• 可重現測試：允許注入 `Random` 實例。

  
  public static void Shuffle(this IList list, Random rng = null)
  {
      rng ??= Random.Shared;
      // ...
  }
  

• 密碼學強度：`RandomNumberGenerator.Create()` 產生隨機索引 (較慢，極高安全需求才需)。

總結

**永遠使用 Fisher-Yates 原地交換** (`Shuffle` 擴充方法)，拒絕 `Insert`、`OrderBy(x => Guid.NewGuid())` (O(n log n) 且分配大量 GUID) 等反模式。標準化、可測試、高效能，三招合一。