如何使用自定义 IComparer 强制对 ArrayList 进行稳定排序？

Question

To perform a stable sort, you must implement a custom IComparer interface.

但是根据this post.

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.

那么有谁知道如何正确地实现 IComparer 以某种方式 'knows' 正在比较的项目的索引？

Answer 1

你可以构建这样的东西（从 this answer by Jon Skeet 借用代码）

public sealed class IdentityEqualityComparer<T> : IEqualityComparer<T>
    where T : class
{
    public int GetHashCode(T value) => RuntimeHelpers.GetHashCode(value);

    public bool Equals(T left, T right) => left == right;
}

public class StableComparer : IComparer
{
    private readonly Dictionary<object, int> _itemsPosition = 
        new Dictionary<object, int>(new IdentityEqualityComparer<object>());

    private readonly IComparer _baseComparer;

    public StableComparer(IEnumerable collection, IComparer baseComparer)
    {
        _baseComparer = baseComparer;

        int index = 0;
        foreach (object item in collection)
        {
            _itemsPosition.Add(item, index);
            index++;
        }
    }

    public int Compare(object x, object y)
    {
        int baseResult = _baseComparer.Compare(x, y);
        if (baseResult != 0)
        {
            return baseResult;
        }

        int xIndex = _itemsPosition[x];
        int yIndex = _itemsPosition[y];

        return xIndex.CompareTo(yIndex);
    }
}

（我添加了相等比较器部分以确保按照@PeterDuniho 的建议使用引用相等）。

这段代码可以这样使用：

class Item
{
    public int Id { get; }
    public string Description { get; }

    public Item(int id, string description)
    {
        Id = id;
        Description = description;
    }
}

class ItemComparer : IComparer
{
    public int Compare(object x, object y) => ((Item)x).Id.CompareTo(((Item)y).Id);
}

和

class Program
{
    static void Main(string[] args)
    {
        var items = new ArrayList()
        {
            new Item(1, "Item 0 (1)"),
            new Item(3, "Item 1 (3)"),
            new Item(2, "Item 2 (2)"),
            new Item(3, "Item 3 (3)"),
            new Item(1, "Item 4 (1)"),
            new Item(4, "Item 5 (4)"),
            new Item(1, "Item 6 (1)")
        };

        Console.WriteLine("Not stable");
        SortAndDisplay((ArrayList)items.Clone(), new ItemComparer());

        Console.WriteLine("Stable");
        SortAndDisplay((ArrayList)items.Clone(), 
          new StableComparer(items, new ItemComparer()));
    }

    static void SortAndDisplay(ArrayList items, IComparer comparer)
    {
        items.Sort(comparer);

        foreach (var item in items)
        {
            Console.WriteLine(((Item)item).Description);
        }
    }
}

请注意，框架 4.5 中的排序发生了变化，可以更改 'equal' 项的排序。如果我运行 Framework 4 中的这段代码，我得到：

Not stable
Item 6 (1)
Item 4 (1)
Item 0 (1)
Item 2 (2)
Item 3 (3)
Item 1 (3)
Item 5 (4)
Stable
Item 0 (1)
Item 4 (1)
Item 6 (1)
Item 2 (2)
Item 1 (3)
Item 3 (3)
Item 5 (4)

我试图 post 将此代码添加到 .net Fiddle 但它不允许使用框架 4。您也可以使用稳定的 Linq's OrderBy。

如何使用自定义 IComparer 强制对 ArrayList 进行稳定排序？

How to force stable sort for ArrayList with a custom IComparer?

c#

sorting

arraylist

stability