2.5.17

2.5.17 #

解答 #

用一个 Wrapper 类包装准备排序的元素，在排序前同时记录元素的内容和下标。

随后对 Wrapper 数组排序，相同的元素会被放在一起，检查它们的下标是否是递增的。

如果不是递增的，则排序算法就是不稳定的；否则排序算法就有可能是稳定的。（不稳定的排序算法也可能不改变相同元素的相对位置，比如用选择排序对有序数组排序）

代码 #

var data = new[] { 7, 7, 4, 8, 8, 5, 1, 7, 7 };
var merge = new MergeSort();
var insertion = new InsertionSort();
var shell = new ShellSort();
var selection = new SelectionSort();
var quick = new QuickSort();

Console.WriteLine("Merge Sort: " + CheckStability(data, merge));
Console.WriteLine("Insertion Sort: " + CheckStability(data, insertion));
Console.WriteLine("Shell Sort: " + CheckStability(data, shell));
Console.WriteLine("Selection Sort: " + CheckStability(data, selection));
Console.WriteLine("Quick Sort: " + CheckStability(data, quick));

bool CheckStability<T>(T[] input, BaseSort sort) where T : IComparable<T>
{
    var items = new Wrapper<T>[input.Length];
    for (var i = 0; i < input.Length; i++)
        items[i] = new Wrapper<T>(i, input[i]);
    sort.Sort(items);
    var index = 0;
    while (index < input.Length - 1)
    {
        while (index < input.Length - 1 && items[index].Key.Equals(items[index + 1].Key))
        {
            if (items[index].Index > items[index + 1].Index)
                return false;
            index++;
        }

        index++;
    }

    return true;
}

internal class Wrapper<T> : IComparable<Wrapper<T>> where T : IComparable<T>
{
    public readonly int Index;
    public T Key;

    public Wrapper(int index, T elements)
    {
        Index = index;
        Key = elements;
    }

    public int CompareTo(Wrapper<T> other)
    {
        return Key.CompareTo(other.Key);
    }
}

另请参阅 #

SortApplication 库