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

Question

我需要以最有效的方式随机"排序"整数列表(0-1999).有任何想法吗？

目前,我正在做这样的事情:

bool[] bIndexSet = new bool[iItemCount];

for (int iCurIndex = 0; iCurIndex < iItemCount; iCurIndex++)
{
    int iSwapIndex = random.Next(iItemCount);
    if (!bIndexSet[iSwapIndex] && iSwapIndex != iCurIndex)
    {
        int iTemp = values[iSwapIndex];
        values[iSwapIndex] = values[iCurIndex];
        values[iCurIndex] = values[iSwapIndex];
        bIndexSet[iCurIndex] = true;
        bIndexSet[iSwapIndex] = true;
    }
}

Answer 1

一个好的线性时间混洗算法是Fisher-Yates shuffle.

您提出的算法可能会遇到的一个问题是,当您接近shuffle的末尾时,您的循环将花费大量时间寻找尚未交换的随机选择的元素.一旦到达交换的最后一个元素,这可能需要不确定的时间.

此外,如果要排序的奇数个元素,您的算法似乎永远不会终止.

Answer 2

static Random random = new Random();

public static IEnumerable<T> RandomPermutation<T>(IEnumerable<T> sequence)
{
    T[] retArray = sequence.ToArray();


    for (int i = 0; i < retArray.Length - 1; i += 1)
    {
        int swapIndex = random.Next(i, retArray.Length);
        if (swapIndex != i) {
            T temp = retArray[i];
            retArray[i] = retArray[swapIndex];
            retArray[swapIndex] = temp;
        }
    }

    return retArray;
}

修改为处理实现IEnumerable的列表或其他对象

Answer 3

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

class Program
{
    static void Main(string[] args)
    {
        IList<int> l = new List<int>();
        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<T> AsRandom<T>(this IList<T> 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)中运行.

Answer 4

正如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)提供足够随机和无偏的结果