列表<T>的行为.在.NET 4.5中的排序从.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已更改排序对象,每个返回列表时维持秩序0的CompareTo.

现在,抛开这个测试的明显疯狂.我知道依靠这种行为是很疯狂的.

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

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

Answer 1

我以前也回答过类似的问题.排序方法已在4.5到4.0之间变化,从快速排序到内省排序.

它实际上更快,但它仍然不是一个稳定的排序¹,也就是说,通过保留相等项的顺序,每次执行具有相同的输出.由于没有实现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参考源,则不然.

_{¹ 使用的混合的定义QuickSort和HeapSort,它应该是一个不稳定的排序.算法的设计者David Musser甚至在他的论文中指出:}

_{像快速排序一样,Introsort不稳定 - 不保留等效元素的顺序 - 因此仍然需要对稳定的排序例程有单独的要求.}

Answer 2

该规范的List.Sort说,使用的排序是不稳定的,因此可能无法维持相等的元素的顺序; 它没有指定相等元素的特定重新排序,因此您无法将此更改称为重大更改.