A stable sort是一种保持具有相同值的元素的相对顺序的排序。
ArrayList.Sort 上的文档说当提供 IComparer
时排序是稳定的:
If comparer is set to null, this method performs a comparison sort (also called an unstable sort); that is, if two elements are equal, their order might not be preserved. In contrast, a stable sort preserves the order of elements that are equal. To perform a stable sort, you must implement a custom IComparer interface.
除非我遗漏了什么,否则以下测试用例表明 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
}
}
我错过了什么吗?如果不是,这是文档错误还是库错误?
显然使用了 OrderBy在 Linq 中给出了稳定的排序。
最佳答案
文档似乎在说,使用 ArrayList.Sort
获得稳定排序的唯一方法是使用以某种方式“知道”排序的 IComparer
正在比较的项目的索引(人们可以想象通过让它在集合上运行初始传递来实现这一点)并将该信息用作其他相等元素的决胜局。
虽然我同意文档的措辞还有很多不足之处,但任何不考虑要比较的项目的索引的旧比较器确实没有意义神奇地将一个固有不稳定的排序算法(Arraylist.Sort
是什么)变成一个稳定的排序算法。
关于c# - ArrayList.Sort 应该是使用 IComparer 的稳定排序,但不是吗?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/5047566/