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給出了穩定的排序。
是否有可能意見的評論可能是「你需要實現你自己的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