LINQ"OrderBy"使用什么排序算法？

Question

显然LINQ的"OrderBy"最初被指定为不稳定,但到Orca时,它被指定为稳定.并非所有文档都已相应更新 - 请考虑以下链接:

但是,如果LINQ的OrderBy现在"稳定",那么这意味着它没有使用快速排序(这本质上是不稳定的),即使某些文档(例如Troy的书)说它是.所以我的问题是:如果不是快速排序,那么LINQ的orderBy使用的实际算法是什么？

Answer 1

对于LINQ to Objects,它是一个稳定的快速排序.对于任何其他类型的LINQ,它留给底层实现.

@Dai IEnumerable <T>是一个接口,所以它实际上取决于底层集合的类型(我不同意@John).例如,List <T>实现IEnumerable <T>,您可以将List <T>声明为IEnumerable <T>.如果您在此列表上执行订单,则使用Linq-to-objects提供程序.另一方面.DbSet <T>还实现了IEnumerable <T>.如果您通过此DbSet执行订单,即使它被声明为IEnumerable,也将使用Linq-to-sql提供程序.如果你想在dbset上使用linq-to-objects,你可以做dbset.AsEnumerable().OrderBy(lambda) (2认同)

Answer 2

启动反射器,打开System.Linq.EnumerableSorter显示Linq2Objects使用快速排序

现在.NET核心向大家开放了:)你为什么不仔细看看？http://referencesource.microsoft.com/#System.Core/System/Linq/Enumerable.cs,1395017e067e5a34 (9认同)

Answer 3

使用Quicksort,但它稳定的原因是因为如果所有键测试相等,则比较每对元素的索引.

换句话说,您可以通过在比较器函数中包含两个元素的原始索引的比较作为回退来使任何快速排序稳定.