在C＃中随机“排序”（随机播放）整数列表的最有效方法

我需要以最有效的方式随机“整理”一列整数（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是一个很好的线性时间混洗算法。

用你提出的算法，你会发现一个问题，就是当你接近洗牌结束时，你的循环会花费大量的时间去寻找那些还没有被交换过的随机选择的元素。 一旦到达交换的最后一个元素，这可能会花费不确定的时间。

此外，看起来像你的算法将永远不会终止，如果有奇数的元素进行排序。

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集合的随机枚举器

 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混洗。 它有点大小（分配4 * list.Count字节），但运行在O（n）。

Answer 4

我不确定效率因素，但是我已经使用类似于以下内容的东西，如果你不反对使用ArrayList：

 private ArrayList ShuffleArrayList(ArrayList source) { ArrayList sortedList = new ArrayList(); Random generator = new Random(); while (source.Count > 0) { int position = generator.Next(source.Count); sortedList.Add(source[position]); source.RemoveAt(position); } return sortedList; } 

使用这个，你不必担心中间交换。

Answer 5

正如Greg指出的那样， Fisher-Yates洗牌将是最好的方法。 这里是来自维基百科的算法的实现：

 public static void shuffle (int[] array) { Random rng = new Random(); // ie, 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）提供足够的随机和无偏的结果

Answer 6

为了提高效率，您可以保留一组已经交换的值/索引，而不是用于指示它们被交换的布尔值。 从剩余的池中挑选随机交换索引。 当池是0，或者当你通过最初的列表，然后你完成。 您没有可能尝试选择随机交换索引值。

当你做一个交换，只需将它们从池中删除。

对于你正在查看的数据大小来说，没有什么大不了的。

Answer 7

 itemList.OrderBy(x=>Guid.NewGuid()).Take(amount).ToList() 

Answer 8

ICR的答案非常快，但是由此产生的阵列没有正常分发。 如果你想要一个正常的分布，这里是代码：

  public static IEnumerable<T> RandomPermutation<T>(this IEnumerable<T> sequence, int start,int end) { T[] array = sequence as T[] ?? sequence.ToArray(); var result = new T[array.Length]; for (int i = 0; i < start; i++) { result[i] = array[i]; } for (int i = end; i < array.Length; i++) { result[i] = array[i]; } var sortArray=new List<KeyValuePair<double,T>>(array.Length-start-(array.Length-end)); lock (random) { for (int i = start; i < end; i++) { sortArray.Add(new KeyValuePair<double, T>(random.NextDouble(), array[i])); } } sortArray.Sort((i,j)=>i.Key.CompareTo(j.Key)); for (int i = start; i < end; i++) { result[i] = sortArray[i - start].Value; } return result; } 

请注意，在我的测试中，这个算法比提供的ICR慢6倍，但是这是我能想到的唯一方法来得到正常的结果分布

Answer 9

会不会有这样的工作？

 var list = new[]{0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15}; var random = new Random(); list.Sort((a,b)=>random.Next(-1,1)); 

Answer 10

我想在Micah的回答中最后两行必须互换。 所以，代码可能看起来像

  public static void shuffle(int[] array) { Random rng = new Random(); // ie, java.util.Random. int n = array.Length; // The number of items left to shuffle (loop invariant). while (n > 1) { int k = rng.Next(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; } } 

Answer 11

关于什么 ：

 System.Array.Sort(arrayinstance, RandomizerMethod); ... //any evoluated random class could do it ! private static readonly System.Random Randomizer = new System.Random(); private static int RandomizerMethod<T>(T x, T y) where T : IComparable<T> { if (x.CompareTo(y) == 0) return 0; return Randomizer.Next().CompareTo(Randomizer.Next()); } 

瞧！

Answer 12

我做了一个使用临时Hashtable的方法，允许Hashtable的自然键类型随机化。 只需添加，阅读和放弃。

 int min = 1; int max = 100; Random random; Hashtable hash = new Hashtable(); for (int x = min; x <= max; x++) { random = new Random(DateTime.Now.Millisecond + x); hash.Add(random.Next(Int32.MinValue, Int32.MaxValue), x); } foreach (int key in hash.Keys) { HttpContext.Current.Response.Write("<br/>" + hash[key] + "::" + key); } hash.Clear(); // cleanup