c# - LINQ 的 OrderBy 如何与 MoveNext 相媲美？

Question

This thread表示 LINQ 的 OrderBy 使用快速排序。考虑到 OrderBy 返回一个 IEnumerable，我正在努力理解它的意义。

我们以下面这段代码为例。

int[] arr = new int[] { 1, -1, 0, 60, -1032, 9, 1 }; 
var ordered = arr.OrderBy(i => i); 
foreach(int i in ordered)
    Console.WriteLine(i); 

循环相当于

var mover = ordered.GetEnumerator();
while(mover.MoveNext())
    Console.WriteLine(mover.Current);

MoveNext() 返回下一个最小的元素。 LINQ 的工作方式，除非您使用 ToList() 或类似方法“兑现”查询，否则不应创建任何中间列表，因此每次调用 MoveNext () IEnumerator 查找下一个最小元素。这没有意义，因为在执行快速排序期间，没有当前最小元素和下一个最小元素的概念。

我的思路哪里出了问题？

Answer 1

the way that LINQ works, unless you "cash out" of the query by use ToList() or similar, there are not supposed to be any intermediate lists created

这个说法是错误的。你的思维缺陷在于你相信了一个错误的陈述。

LINQ to Objects 实现很聪明地以合理的成本延迟工作。正如您正确注意到的那样，在排序的情况下是不可能的。 OrderBy 生成一个对象作为其结果，当调用 MoveNext 时，该对象枚举整个源序列，在内存中生成排序列表，然后枚举排序列表。

同样，连接和分组也必须在枚举第一个元素之前枚举整个序列。 (逻辑上，连接只是带有过滤器的叉积，工作可以分布在每个 MoveNext() 上，但效率很低；为了实用，构建了一个查找表。它是计算渐近空间与时间权衡的教育意义；试一试。)

源代码可用；如果您对实现有疑问，我鼓励您阅读它。或者查看 Jon 的“edulinq”系列。