26

我在针对 .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保持顺序。0CompareTo

现在，抛开这个测试明显的疯狂。我知道依赖这种行为是很疯狂的。

这肯定是一个突破性的变化吗？本页未列出.NET 4.0 和 4.5 之间的兼容性。

是否有一个原因？我错过了什么吗？是否有另一个页面显示实际的重大更改？我应该坐下来停止恐慌吗？

4

6 回答 6

36

我之前回答过类似的问题。排序方法在 4.5 和 4.0 之间发生了变化，从快速排序变为内省排序。

它实际上更快，但它仍然不是稳定的排序1，也就是说，通过保留相等项的顺序，每次执行都具有相同的输出。由于没有实现List.Sort是一种稳定的排序，我认为您运行单元测试的次数不够多，以至于在两个运行时都会出错？

我尝试使用等效代码和返回 0 的比较器自己重现它。在 .NET 4.5 和 .NET 3.5 中，有时会保留列表顺序，有时则不会。

即使它确实将排序类型从稳定更改为不稳定，也不是重大更改。使用的排序类型和确切的输出不是List.Sort. 方法合同保证的所有内容是您的项目将根据使用的比较器按排序顺序排列。

不过，这很有趣，因为 [MSDN 文档](http://msdn.microsoft.com/en-us/library/b0zbh7b6.aspx) 仍然说它使用 QuickSort（通过 `Array.Sort`），但这是如果您要逐步浏览 .NET 参考源，情况并非如此。

1 根据使用 和 混合的定义QuickSort，HeapSort它应该是一种不稳定的排序。甚至该算法的设计者 David Musser 在他的论文中也表示：

Introsort 和快速排序一样，是不稳定的——不保留等价元素的顺序——因此仍然需要对稳定的排序例程有单独的要求。

于 2012-09-17T14:54:55.793 回答
5

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

于 2012-09-17T14:33:20.920 回答
3

正如@Rawling 所说，请查看以下文档Sort()：

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

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

于 2012-09-17T14:36:54.570 回答
2

我没有看到任何变化。正如其他人已经写的那样，两个版本都执行不稳定的排序。这意味着您不能依赖相等比较的元素的顺序。他们的顺序在排序过程中可能会或可能不会改变。这当然不是一个突破性的变化。

请参阅：List< T >.Sort 的文档

于 2012-09-17T14:40:02.603 回答
1

来自MSDN

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

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

于 2012-09-17T14:36:48.630 回答
0

像这样的问题经常会出现新的框架版本。这里和这里有一些用于 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.

于 2013-09-24T11:24:35.027 回答