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 上的文档说，当<提供排序稳定的c0>:

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?

显然使用

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屋！