用.NET随机化字符串数组的最佳方法是什么？我的数组包含大约500个字符串，我想用相同的字符串但以随机顺序创建一个新的" Array"。

请在答案中包含一个Cexample。

解决方案

生成相同长度的随机浮点或者整数数组。对该数组进行排序，然后在目标数组上进行相应的交换。

这产生了真正独立的排序。

随机化数组非常费力，因为我们必须绕一堆字符串移动。为什么不只是从数组中随机读取？在最坏的情况下，我们甚至可以使用getNextString()创建包装器类。如果确实需要创建随机数组，则可以执行以下操作

for i = 0 -> i= array.length * 5
   swap two strings in random places

• 5是任意的。

该算法简单但效率不高，O(N2)。所有"排序依据"算法通常为O(N log N)。在成千上万个元素以下，它可能没有什么区别，但对于大型列表而言，它不会起作用。

var stringlist = ... // add your values to stringlist

var r = new Random();

var res = new List<string>(stringlist.Count);

while (stringlist.Count >0)
{
   var i = r.Next(stringlist.Count);
   res.Add(stringlist[i]);
   stringlist.RemoveAt(i);
}

它是O(N2)的原因很微妙：List.RemoveAt()是O(N)操作，除非我们从头开始依次删除。

如果我们使用的是.NET 3.5，则可以使用以下IEnumerable凉爽性(VB.NET，而不是C＃，但思路应该很清楚...)：

Random rnd=new Random();
string[] MyRandomArray = MyArray.OrderBy(x => rnd.Next()).ToArray();

编辑：确定，这是相应的VB.NET代码：

Dim rnd As New System.Random
Dim MyRandomArray = MyArray.OrderBy(Function() rnd.Next)

第二次编辑，以回应由于返回基于时间的序列而导致System.Random"不是线程安全的"并且"仅适用于玩具应用程序"：如在我的示例中所使用的，Random()完全是线程安全的，除非我们允许在其中重新随机化数组的例程重新进入，在这种情况下，无论如何我们都需要诸如lock(MyRandomArray)之类的东西，以免破坏数据，这也将保护rnd 。

同样，应该很好地理解System.Random作为熵的来源不是很强大。如MSDN文档中所述，如果要进行与安全相关的任何操作，则应使用从System.Security.Cryptography.RandomNumberGenerator派生的内容。例如：

using System.Security.Cryptography;

...

RNGCryptoServiceProvider rnd = new RNGCryptoServiceProvider();
string[] MyRandomArray = MyArray.OrderBy(x => GetNextInt32(rnd)).ToArray();

...

static int GetNextInt32(RNGCryptoServiceProvider rnd)
    {
        byte[] randomInt = new byte[4];
        rnd.GetBytes(randomInt);
        return Convert.ToInt32(randomInt[0]);
    }

只是想着我的脑袋，我们可以执行以下操作：

public string[] Randomize(string[] input)
{
  List<string> inputList = input.ToList();
  string[] output = new string[input.Length];
  Random randomizer = new Random();
  int i = 0;

  while (inputList.Count > 0)
  {
    int index = r.Next(inputList.Count);
    output[i++] = inputList[index];
    inputList.RemoveAt(index);
  }

  return (output);
}

Random r = new Random();
List<string> list = new List(originalArray);
List<string> randomStrings = new List();

while(list.Count > 0)
{
int i = r.Random(list.Count);
randomStrings.Add(list[i]);
list.RemoveAt(i);
}

我们正在寻找一种改组算法，对吗？

好的，有两种方法可以做到这一点：聪明但人们总是似乎误解了它并弄错了，所以也许它毕竟不是那个聪明的人方式，而愚蠢的人却因为它的工作原理而在乎。

哑巴方式

Create a duplicate of your first array, but tag each string should with a random number.
  Sort the duplicate array with respect to the random number.

此算法效果很好，但是请确保随机数生成器不太可能标记具有相同数字的两个字符串。由于发生了所谓的生日悖论，因此发生这种情况的频率超出了预期。它的时间复杂度为O(n log n)。

聪明的方法

我将其描述为递归算法：

To shuffle an array of size n (indices in the range [0..n-1]):
  
  if n = 0
  
  
  do nothing
  
  
  if n > 0
  
  
  (recursive step) shuffle the first n-1 elements of the array
  choose a random index, x, in the range [0..n-1]
  swap the element at index n-1 with the element at index x

迭代等效项是使迭代器遍历数组，并在进行过程中与随机元素交换，但请注意，在迭代器指向的元素之后，我们不能与元素交换。这是一个非常常见的错误，会导致随机播放。

时间复杂度为O(n)。

这是使用OLINQ的一种简单方法：

// Input array
List<String> lst = new List<string>();
for (int i = 0; i < 500; i += 1) lst.Add(i.ToString());

// Output array
List<String> lstRandom = new List<string>();

// Randomize
Random rnd = new Random();
lstRandom.AddRange(from s in lst orderby rnd.Next(100) select s);

以下实现使用Fisher-Yates算法。它运行时间为O(n)，并在适当位置随机播放，因此尽管"代码随机排序"技术更多，但其性能要优于"随机排序"技术。有关一些比较性能的测量，请参见此处。我使用了System.Random，它适合用于非加密目的。*

static class RandomExtensions
{
    public static void Shuffle<T> (this Random rng, T[] array)
    {
        int n = array.Length;
        while (n > 1) 
        {
            int k = rng.Next(n--);
            T temp = array[n];
            array[n] = array[k];
            array[k] = temp;
        }
    }
}

用法：

var array = new int[] {1, 2, 3, 4};
new Random().Shuffle(array);

*对于更长的数组，为了使(极大)数量的排列具有同等可能性，有必要通过多次迭代来运行伪随机数生成器(PRNG)，以使每次交换产生足够的熵。对于500个元素的数组，仅是可能的500中的很小一部分！使用PRNG可以获得排列。尽管如此，Fisher-Yates算法没有偏见，因此混洗效果与我们使用的RNG一样好。

Jacco，解决方案使用自定义IComparer是不安全的。排序例程要求比较器符合多项要求才能正常运行。其中首先是一致性。如果在同一对对象上调用比较器，则它必须始终返回相同的结果。 (比较也必须是可传递的)。

不满足这些要求会导致排序例程中出现许多问题，包括无限循环的可能性。

关于将随机数值与每个条目相关联然后按该值排序的解决方案，这会导致输出中的固有偏差，因为每当两个条目被分配相同的数值时，输出的随机性就会受到损害。 (在"稳定"排序例程中，以输入中的第一者为准，将以输出中的第一者为准。Array.Sort并非稳定，但基于Quicksort算法进行的分区仍然存在偏差。)

我们需要考虑所需的随机性级别。如果我们在一个扑克网站上需要加密的随机性级别，以保护自己免受确定的攻击者的侵害，则要求与只希望随机分配歌曲播放列表的用户有很大不同。

对于歌曲列表混排，使用种子PRNG(例如System.Random)没有问题。对于一个扑克网站，它甚至都不是一种选择，我们需要比任何人在stackoverflow上为我们解决的问题都更加难以思考这个问题。 (使用加密的RNG只是开始，我们需要确保算法不会引入偏差，具有足够的熵源并且不会暴露任何会损害后续随机性的内部状态)。

使用Durstenfeld的Fisher-Yates改组实现，此帖子已经得到了很好的回答，从而获得了快速而公正的结果。甚至已经发布了一些实现，尽管我注意到其中一些实际上是不正确的。

不久前，我写了几篇文章，内容涉及使用这种技术实现全部和部分混洗，(第二条链接是我希望在其中增加价值的地方)，还有一篇后续文章，介绍了如何检查实现是否公正，可以用来检查任何随机播放算法。我们可以在第二篇文章的末尾看到一个简单错误对随机数选择的影响。

我们也可以使用Matt Howells进行扩展。例子。

namespace System
    {
        public static class MSSystemExtenstions
        {
            private static Random rng = new Random();
            public static void Shuffle<T>(this T[] array)
            {
                rng = new Random();
                int n = array.Length;
                while (n > 1)
                {
                    int k = rng.Next(n);
                    n--;
                    T temp = array[n];
                    array[n] = array[k];
                    array[k] = temp;
                }
            }
        }
    }

然后，我们可以像这样使用它：

string[] names = new string[] {
                "Aaron Moline1", 
                "Aaron Moline2", 
                "Aaron Moline3", 
                "Aaron Moline4", 
                "Aaron Moline5", 
                "Aaron Moline6", 
                "Aaron Moline7", 
                "Aaron Moline8", 
                "Aaron Moline9", 
            };
        names.Shuffle<string>();