LINQ Quicksort除了级联时不稳定

Question

在"使用C#4.0 LINQ To Objects"的第64页(Tony Magennis),他说LINQ的快速排序算法不稳定......

...虽然这可以通过将结果级联到ThenBy或ThenByDescending运算符来解决.

咦？为什么将不稳定的分类级联到另一个分类会修复结果？事实上,我认为这是不可能的.原始订单一旦通过不稳定的排序,就会丢失.我在这里错过了什么？

Answer 1

简单地说,他错了.Linq OrderBy 等人.方法记录为执行稳定排序:

该方法执行稳定的排序; 也就是说,如果两个元素的键相等,则保留元素的顺序.相反,不稳定的排序不会保留具有相同键的元素的顺序.

Answer 2

不稳定排序意味着一系列x.OrderBy(...).OrderBy(...)调用只能根据最终标准进行可靠排序.x.OrderBy(...).ThenBy(...)在应用新排序顺序时显式捕获先前排序顺序的知识.我相信通过电话来做到这一点IOrderedEnumerable<TElement>.CreateOrderedEnumerable<TKey>,尽管我不是100%肯定这一点.

编辑:只是要清楚,当我说,"捕获知识......"我并不是说第一个OrderBy执行排序,不知何故第二个知道它做了什么.请记住,OrderBy返回一个IOrderedEnumerable<T>,在任何人尝试使用元素之前,它根本不执行任何工作.在这种情况下,它永远不会执行排序,因为ThenBy使用的知识,如何OrderBy 将已经整理,建,在预期的方式在一个单一的步骤既适用的排序顺序一个全新的分拣机.

有人指出,Magennis在不稳定的事情上是错误的.然而,以上描述仍然有效.