使用Random和OrderBy作为洗牌算法是一个好的选择吗？

我认为这里很多答案都是错误的，比如“该算法通过为列表中的每个值生成一个新的随机值，然后按照这些随机值对列表进行排序”。

我认为这并没有给源集合的每个元素分配一个随机值。相反，可能会运行像快速排序这样的排序算法，它将调用一个比较函数大约n log n次。有些排序算法确实希望这个比较函数是稳定的，并且总是返回相同的结果！

难道不能让IEnumerableSorter在每个算法步骤中调用一个比较函数，例如快速排序，并且每次都使用x => r.Next()函数调用两个参数而不缓存它们吗？

如果是这样的话，你可能会真正搞砸排序算法，使它比算法预期的要糟糕得多。当然，它最终会变得稳定并返回一些东西。

我可以稍后通过在一个新的“Next”函数中放置调试输出来检查它，看看会发生什么。在Reflector中，我无法立即找出它的工作原理。

值得注意的是，由于LINQ的延迟执行特性，使用带有OrderBy()的随机数生成器实例可能会导致可能出乎意料的行为：排序直到集合被读取才发生。这意味着每次读取或枚举集合时，顺序都会改变。人们可能期望元素被洗牌一次，然后在以后的访问中保留顺序。

---

Random random = new();
var shuffled = ordered.OrderBy(x => random.Next())

上面的代码将一个 lambda 函数 x => random.Next() 作为参数传递给了 OrderBy()。这将会 捕获 被 random 引用的实例，并将其与 lambda 一起保存，以便稍后可以调用此实例上的 Next() 来执行排序，这发生在枚举之前（当从集合请求第一个元素时）。
问题在于，由于此执行被保存以供稍后使用，因此每次在使用通过调用相同随机实例上的 Next() 获取的新数字进行枚举之前，都会发生排序。

---

示例

为了演示这种行为，我使用了Visual Studio的C#交互式Shell：

> List<int> list = new() { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
> Random random = new();
> var shuffled = list.OrderBy(element => random.Next());
> shuffled.ToList()
List<int>(10) { 5, 9, 10, 4, 6, 2, 8, 3, 1, 7 }   
> shuffled.ToList()
List<int>(10) { 8, 2, 9, 1, 3, 6, 5, 10, 4, 7 } // Different order
> shuffled.ElementAt(0) 
9                                              // First element is 9
> shuffled.ElementAt(0)
7                                              // First element is now 7
> 

这种行为甚至可以通过在使用Visual Studio调试器时在IOrderedEnumerable创建之后的断点处进行观察：每次悬停在变量上时，元素以不同的顺序显示。

---

当然，如果您立即通过调用ToList()或等效方法枚举元素，则不适用此规则。但是，在许多情况下，这种行为可能会导致错误，其中之一是当预期混洗的集合在每个索引处都包含唯一元素时。

启动时间在清除所有线程和缓存每个新测试的代码上运行，

第一个不成功的代码。它在LINQPad上运行。如果您遵循测试此代码。

Stopwatch st = new Stopwatch();
st.Start();
var r = new Random();
List<string[]> list = new List<string[]>();
list.Add(new String[] {"1","X"});
list.Add(new String[] {"2","A"});
list.Add(new String[] {"3","B"});
list.Add(new String[] {"4","C"});
list.Add(new String[] {"5","D"});
list.Add(new String[] {"6","E"});

//list.OrderBy (l => r.Next()).Dump();
list.OrderBy (l => Guid.NewGuid()).Dump();
st.Stop();
Console.WriteLine(st.Elapsed.TotalMilliseconds);

list.OrderBy(x => r.Next()) 使用了 38.6528 毫秒

list.OrderBy(x => Guid.NewGuid()) 使用了 36.7634 毫秒（这是从 MSDN 推荐的方法）

第二次之后，它们都使用相同的时间。

编辑： 在 Intel Core i7 4@2.1GHz、8 GB DDR3 @1600 内存、HDD SATA 5200 rpm 上进行测试，数据来源：[Data: www.dropbox.com/s/pbtmh5s9lw285kp/data]

using System;
using System.Runtime;
using System.Diagnostics;
using System.IO;
using System.Collections.Generic;
using System.Collections;
using System.Linq;
using System.Threading;
namespace Algorithm
{
    class Program
    {
        public static void Main(string[] args)
        {
            try {
                int i = 0;
                int limit = 10;
                var result = GetTestRandomSort(limit);
                foreach (var element in result) {
                    Console.WriteLine();
                    Console.WriteLine("time {0}: {1} ms", ++i, element);
                }
            } catch (Exception e) {
                Console.WriteLine(e.Message);
            } finally {
                Console.Write("按任意键继续. . . ");
                Console.ReadKey(true);
            }
        }
 public static IEnumerable<double> GetTestRandomSort(int limit)
        {
            for (int i = 0; i < 5; i++) {
                string path = null, temp = null;
                Stopwatch st = null;
                StreamReader sr = null;
                int? count = null;
                List<string> list = null;
                Random r = null;
GC.Collect();
                GC.WaitForPendingFinalizers();
                Thread.Sleep(5000);
st = Stopwatch.StartNew();
                #region 导入输入数据
                path = Environment.CurrentDirectory + "\\data";
                list = new List<string>();
                sr = new StreamReader(path);
                count = 0;
                while (count < limit && (temp = sr.ReadLine()) != null) {
//                  Console.WriteLine(temp);
                    list.Add(temp);
                    count++;
                }
                sr.Close();
                #endregion
//              Console.WriteLine("--------------随机排序--------------");
//              #region 使用OrderBy(random.Next())进行随机排序
//              r = new Random();
//              list = list.OrderBy(l => r.Next()).ToList();
//              #endregion
//              #region 使用OrderBy(Guid)进行随机排序
//              list = list.OrderBy(l => Guid.NewGuid()).ToList();
//              #endregion
//              #region 使用Parallel和OrderBy(random.Next())进行随机排序
//              r = new Random();
//              list = list.AsParallel().OrderBy(l => r.Next()).ToList();
//              #endregion
//              #region 使用Parallel和OrderBy(Guid)进行随机排序
//              list = list.AsParallel().OrderBy(l => Guid.NewGuid()).ToList();
//              #endregion
//              #region 使用用户定义的Shuffle方法进行随机排序
//              r = new Random();
//              list = list.Shuffle(r).ToList();
//              #endregion
//              #region 使用Parallel和用户定义的Shuffle方法进行随机排序
//              r = new Random();
//              list = list.AsParallel().Shuffle(r).ToList();
//              #endregion
// 结果
//              
                st.Stop();
                yield return st.Elapsed.TotalMilliseconds;
                foreach (var element in list) {
                Console.WriteLine(element);
            }
            }
}
    }
}

结果描述：https://www.dropbox.com/s/9dw9wl259dfs04g/ResultDescription.PNG
结果统计：https://www.dropbox.com/s/ewq5ybtsvesme4d/ResultStat.PNG

结论：
假设：在第一个解决方案中，LINQ OrderBy(r.Next())和OrderBy(Guid.NewGuid())不比用户定义的Shuffle方法差。

答案：它们是矛盾的。