.NET 4.5中List<T>.Sort的行为与.NET 4.0有何改变？

Question

在针对.NET 4.0的项目中，我有以下测试：

[TestFixture]
public class Donkey
{
    [Test]
    public void TestListSorting()
    {
        var expected = new[]
                    {
                                MockRepository.GenerateStub<IComparable>(),
                                MockRepository.GenerateStub<IComparable>()
                    };

        var sorted = new List<IComparable>(expected);

        CollectionAssert.AreEqual(expected, sorted);
        sorted.Sort();
        CollectionAssert.AreEqual(expected, sorted);

    }
}

如果我在只安装了 .NET 4.0 的机器上运行它，它会失败。 如果我在只安装了 .NET 4.5 的机器上运行它，它会通过。

我假设在 .NET 4.5 中，Sort 的实现已更改为在对返回 CompareTo 的每个对象进行排序时保持顺序。

现在，请暂且不考虑这个测试的明显疯狂之处。我知道依赖这种行为是疯狂的。

这难道不是一项破坏性的变化吗？它没有列在关于 .NET 4.0 和 4.5 兼容性的此页面中。

这是有原因的吗？我有什么遗漏吗？是否有另一页显示实际的破坏性变化？我应该坐下来停止恐慌吗？

- jonnystoten

---

该规范（http://msdn.microsoft.com/en-us/library/b0zbh7b6(v=vs.110).aspx）仍然说明它使用的是快速排序，可能无法保持顺序。 - Rawling

虽然你不是第一个注意到的。（还有这个提到它被改成了“内省排序”，这不是稳定的，但是是另一种算法。） - Rawling

可能发生的情况是，快速排序被修改了，以使这种微不足道的排序看起来稳定。（也许是选择了不同的枢轴。）我不确定如何构建一个测试用例来证明使用的排序算法现在是否稳定，但比较两个元素并不是解决方法。 - millimoose

另一种查看差异的方法是 var li = new List<string> { "first", "second", }; li.Sort((x, y) => 0);。 - Jeppe Stig Nielsen

Answer 1

我之前回答过一个类似的问题。在4.5和4.0之间，排序方法已经从快速排序更改为内省排序。

实际上，它更快了，但仍然不是一个稳定的排序¹，也就是说，对于相等的项，每次执行都保留相同的输出顺序。由于没有任何List.Sort的实现是稳定排序，我认为你还没有运行足够多次以上的单元测试来使其在两个运行时中都出错？

我尝试使用等效代码和返回0的比较器来复制它。有时列表顺序被保留，有时不被保留，在.NET 4.5和.NET 3.5中都是如此。

即使它把排序类型从稳定变成不稳定，这也不是一个破坏性的变化。使用的排序类型和确切输出并不是List.Sort合同的一部分。方法合同所保证的仅仅是您的项目将按照所使用的比较器进行排序。

---

_{¹ 根据使用QuickSort和HeapSort的混合定义，这应该是一种不稳定的排序方法。即使是算法设计者David Musser在他的论文中也指出：}

_{Introsort，像quicksort一样，不稳定--不能保留等价元素的顺序--因此仍需要单独要求一个稳定的排序程序。}

- Christopher Currens

---

+1：谢谢你在其他答案中提供的精彩解释。我反应有点慢，所以在阅读了你的解释之前，我对下面的其他答案一无所知。 - JohnB

自本答案撰写之后，MSDN文档已更新以反映此更改。 - Lucas

Answer 2

List.Sort 的规范指出所使用的排序是不稳定的，因此可能无法保留相等元素的顺序。它没有指定相等元素的特定重新排序方式，因此您不能真正将此更改称为破坏性更改。

- Rawling

Answer 3

如@Rawling所说，请参考Sort()的文档：

该实现执行不稳定排序；即，如果两个元素相等，则它们的顺序可能不会被保留。

因此，您正在尝试测试明确定义为未定义的内容。这不是一种破坏性的变化。

- svick

Answer 4

我看不到任何变化。正如其他人已经写过的，这两个版本都执行不稳定的排序。这意味着您不能依赖于比较相等的元素的顺序。在排序期间，它们的顺序可能会更改或者可能不会更改。这肯定不是一个破坏性的变化。

参见：List<T>.Sort 文档

- Tomek Szpakowicz

Answer 5

来自MSDN

此实现执行不稳定的排序；也就是说，如果两个元素相等，则它们的顺序可能不会被保留

看起来顺序不可靠，因此测试无效。另外，为什么要测试Sort方法呢？对我来说似乎是一个不必要的测试。

- James

Answer 6

这样的问题通常会在新框架版本中出现。有一些针对3.5→4.0转换的这里和这里。

对于这个特定版本的更改，差异已经在数组或List<>的两个元素中出现，就像你的问题所示。另一个简单的例子是：

using System;
using System.Linq;

namespace SortTest
{
  static class Program
  {
    static void Main()
    {
      var arr = new[] { new { Name = "Mary", Age = 17, }, new { Name = "Louise", Age = 17, }, };

      Array.Sort(arr, (x, y) => x.Age.CompareTo(y.Age));

      Console.WriteLine(string.Join(",", arr.Select(x => x.Name)));
    }
  }
}

在 .NET 4.0 中，这将打印 Louise,Mary。元素被交换了。然而，在 .NET 4.5 中，它打印 Mary,Louise。请注意，这两个女孩年龄相同。

List<>.Sort 实例方法和 Array.Sort 静态方法被记录为非稳定排序。它们可以以任何顺序留下相等的“大小”元素。因此，您的代码不能对等价元素的顺序做出任何假设。

相比之下，Linq 的 OrderBy 方法执行稳定排序。所以

var ordered = arr.OrderBy(x => x.Age);

如果Mary和Louise的Age相同，则必须不交换它们。

- Jeppe Stig Nielsen