ArrayList.Sort 应该是带有 IComparer 的稳定排序，但不是? [英] ArrayList.Sort should be a stable sort with an IComparer but is not?

问题描述

稳定排序 是一种保持元素相对顺序的排序相同的值.

A stable sort is a sort that maintains the relative ordering of elements with the same value.

ArrayList.Sort 上的文档说，当 IComparer 提供了稳定的排序:

The docs on ArrayList.Sort say that when an IComparer is provided the sort is stable:

如果 comparer 设置为 null，则此方法执行比较排序(也称为不稳定排序)；也就是说，如果两个元素相等，它们的顺序可能不会被保留.相反，稳定排序保留相等元素的顺序.要执行稳定排序，您必须实现自定义 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 没有使用稳定的排序:

Unless I'm missing something, the following testcase shows that ArrayList.Sort is not using a stable 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
    }
}

我错过了什么吗?如果不是，这是文档错误还是库错误?

Am I missing something? If not, would this be a documentation bug or a library bug?

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

Apparently using an OrderBy in Linq gives a stable sort.

推荐答案

文档似乎在说，使用 ArrayList.Sort 获得稳定排序的唯一方法是使用IComparer 以某种方式知道"正在比较的项目的索引(人们可以想象通过让它在集合上运行初始传递来实现这一点)并使用该信息作为其他情况的决胜局等元素.

What the documentation appears to be saying is that the only way you can get a stable sort with ArrayList.Sort is to use an IComparer that somehow 'knows' the indices of the items that are being compared (one would imagine accomplishing this by making it run an initial pass on the collection) and uses that information as a tie-breaker for otherwise equal elements.

虽然我同意文档的措辞有很多不足之处，但任何不考虑要比较项的索引的旧比较器确实没有任何意义神奇地将固有不稳定的排序算法(这就是Arraylist.Sort)变成稳定的排序算法.

Although I agree that the phrasing of the documentation leaves much to be desired, it really doesn't make sense that any old comparer that doesn't consider the indices of the items to be compared can magically turn an inherently unstable sorting algorithm (which is what Arraylist.Sort is) into a stable one.

这篇关于ArrayList.Sort 应该是带有 IComparer 的稳定排序，但不是?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！