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排序，但不是？

回答

相關問題