为什么List <T> .Sort方法重新排序相同的IComparable <T>元素？

Question

我对List Sort方法如何处理排序有疑问.鉴于以下要素:

class Element : IComparable<Element>
{
    public int Priority { get; set; }
    public string Description { get; set; }

    public int CompareTo(Element other)
    {
        return Priority.CompareTo(other.Priority);
    }
}

如果我尝试这样排序:

List<Element> elements = new List<Element>()
                             {
                                 new Element()
                                     {
                                         Priority = 1,
                                         Description = "First"
                                     },
                                 new Element()
                                     {
                                         Priority = 1,
                                         Description = "Second"
                                     },
                                 new Element()
                                     {
                                         Priority = 2,
                                         Description = "Third"
                                     }
                             };
elements.Sort();

然后第一个元素是先前的第二个元素"Second".或者,换句话说,这个断言失败了:

Assert.AreEqual("First", elements[0].Description);

当元素基本相同时,为什么.NET重新排序我的列表？如果比较返回非零值,我希望它只对列表重新排序.

Answer 1

从MSDN的List.Sort()方法的文档:

此方法使用Array.Sort,它使用QuickSort算法.此实现执行不稳定的排序; 也就是说,如果两个元素相等,则可能不会保留它们的顺序.相反,稳定的排序保留了相等元素的顺序.

这是链接:http: //msdn.microsoft.com/en-us/library/b0zbh7b6.aspx

从本质上讲,排序按设计和记录执行.

Answer 2

这是一个扩展方法SortStable()List<T> where T : IComparable<T>:

public static void SortStable<T>(this List<T> list) where T : IComparable<T>
{
    var listStableOrdered = list.OrderBy(x => x, new ComparableComparer<T>()).ToList();
    list.Clear();
    list.AddRange(listStableOrdered);
}

private class ComparableComparer<T> : IComparer<T> where T : IComparable<T>
{
    public int Compare(T x, T y)
    {
        return x.CompareTo(y);
    }
}

测试:

[Test]
public void SortStable()
{
    var list = new List<SortItem>
                    {
                        new SortItem{ SortOrder = 1, Name = "Name1"},
                        new SortItem{ SortOrder = 2, Name = "Name2"},
                        new SortItem{ SortOrder = 2, Name = "Name3"},
                    };

    list.SortStable();

    Assert.That(list.ElementAt(0).SortOrder, Is.EqualTo(1));
    Assert.That(list.ElementAt(0).Name, Is.EqualTo("Name1"));
    Assert.That(list.ElementAt(1).SortOrder, Is.EqualTo(2));
    Assert.That(list.ElementAt(1).Name, Is.EqualTo("Name2"));
    Assert.That(list.ElementAt(2).SortOrder, Is.EqualTo(2));
    Assert.That(list.ElementAt(2).Name, Is.EqualTo("Name3"));
}

private class SortItem : IComparable<SortItem>
{
    public int SortOrder { get; set; }
    public string Name { get; set; }

    public int CompareTo(SortItem other)
    {
        return SortOrder.CompareTo(other.SortOrder);
    }
}

在测试方法中,如果调用Sort()方法而不是SortStable(),则可以看到测试失败.