在C#中随机"排序"(随机播放)整数列表的最有效方法

我们可以使用这个扩展方法来获取任何IList集合的Random枚举器

class Program
{
    static void Main(string[] args)
    {
        IList l = new List();
        l.Add(7);
        l.Add(11);
        l.Add(13);
        l.Add(17);

        foreach (var i in l.AsRandom())
            Console.WriteLine(i);

        Console.ReadLine();
    }
}


public static class MyExtensions
{
    public static IEnumerable AsRandom(this IList list)
    {
        int[] indexes = Enumerable.Range(0, list.Count).ToArray();
        Random generator = new Random();

        for (int i = 0; i < list.Count; ++i )
        {
            int position = generator.Next(i, list.Count);

            yield return list[indexes[position]];

            indexes[position] = indexes[i];
        }
    }
}   

这在我们想要随机枚举的列表的索引上使用反向Fisher-Yates shuffle.它有点大小(分配4*list.Count字节),但在O(n)中运行.

正如Greg指出的那样,Fisher-Yates洗牌将是最好的方法.以下是维基百科的算法实现:

public static void shuffle (int[] array)
{
   Random rng = new Random();   // i.e., java.util.Random.
   int n = array.length;        // The number of items left to shuffle (loop invariant).
   while (n > 1)
   {
      int k = rng.nextInt(n);  // 0 <= k < n.
      n--;                     // n is now the last pertinent index;
      int temp = array[n];     // swap array[n] with array[k] (does nothing if k == n).
      array[n] = array[k];
      array[k] = temp;
   }
}

上面的实现依赖于Random.nextInt(int)提供足够随机和无偏的结果