ArrayList.Sort应该是一个稳定的IComparer排序，但不是？

A stable sort是一种维护具有相同值的元素的相对顺序的排序。ArrayList.Sort应该是一个稳定的IComparer排序，但不是？

上ArrayList.Sort的文档说的是，当提供了一种IComparer排序是稳定的：

如果比较器被设置为无效，则此方法的排序执行比较（也称为不稳定排序）;也就是说，如果两个元素相等，他们的顺序可能不会被保留。相反，稳定的排序保留了相同元素的顺序。要执行稳定的排序，您必须实现一个自定义的IComparer接口。

除非我失去了一些东西，下面的测试用例显示ArrayList.Sort没有使用一个稳定的排序：

internal class DisplayOrdered { 
    public int ID { get; set; } 
    public int DisplayOrder { get; set; } 
    public override string ToString() { 
     return string.Format("ID: {0}, DisplayOrder: {1}", ID, DisplayOrder); 
    } 
} 

internal class DisplayOrderedComparer : IComparer { 
    public int Compare(object x, object y) { 
     return ((DisplayOrdered)x).DisplayOrder - ((DisplayOrdered)y).DisplayOrder; 
    } 
} 

[TestFixture] 
public class ArrayListStableSortTest { 

    [Test] 
    public void TestWeblinkCallArrayListIsSortedUsingStableSort() { 
     var call1 = new DisplayOrdered {ID = 1, DisplayOrder = 0}; 
     var call2 = new DisplayOrdered {ID = 2, DisplayOrder = 0}; 
     var call3 = new DisplayOrdered {ID = 3, DisplayOrder = 2}; 
     var list = new ArrayList {call1, call2, call3}; 

     list.Sort(new DisplayOrderedComparer()); 

     // expected order (by ID): 1, 2, 3 (because the DisplayOrder 
     // is equal for ID's 1 and 2, their ordering should be 
     // maintained for a stable sort.) 
     Assert.AreEqual(call1, list[0]); // Actual: ID=2 ** FAILS 
     Assert.AreEqual(call2, list[1]); // Actual: ID=1 
     Assert.AreEqual(call3, list[2]); // Actual: ID=3 
    } 
}

我缺少的东西？如果没有，这是文档错误还是库错误？

Linq显然使用OrderBy给出了稳定的排序。

来源

2011-02-18 Kaleb Pederson

是否有可能意见的评论可能是“你需要实现你自己的IComparer，迫使排序稳定”，而不是“如果你实现自己的IComparer，排序会隐含稳定”？ – BlueMonkMN 2011-02-18 23:21:30

这不是实施比较的好方法。 http://blogs.msdn.com/b/ericlippert/archive/2011/01/27/spot-the-defect-bad-comparisons-part-three.aspx – 2011-02-18 23:21:32

什么文件似乎说的是，你可以得到ArrayList.Sort稳定排序的唯一方法是使用某种方式“知道”的IComparer被比较的项目的索引（一个想象通过完成此使其对该集合进行初始传递），并将该信息用作其他方面相等元素的平局。

虽然我同意文件的措辞极不理想了，它真的没有意义，任何旧的比较器是不考虑项目的指标进行比较可以神奇地把一个固有的不稳定的排序算法（这是什么Arraylist.Sort）是一个稳定的。

来源

2011-02-18 23:24:10 Ani

ArrayList.Sort应该是一个稳定的IComparer排序，但不是？

回答

相关问题