2.5.17

上次更新:2019-04-17
发现了题解错误/代码缺陷/排版问题?请点这里:如何:提交反馈

解答

用一个 Wrapper 类包装准备排序的元素,在排序前同时记录元素的内容和下标。
随后对 Wrapper 数组排序,相同的元素会被放在一起,检查它们的下标是否是递增的。
如果不是递增的,则排序算法就是不稳定的;否则排序算法就有可能是稳定的。
(不稳定的排序算法也可能不改变相同元素的相对位置,比如用选择排序对有序数组排序)

代码

using System;
using SortApplication;

namespace _2._5._17
{
    class Program
    {
        class Wrapper<T> : IComparable<Wrapper<T>> where T : IComparable<T>
        {
            public int Index;
            public T Key;

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

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

        static void Main(string[] args)
        {
            int[] data = new int[] { 7, 7, 4, 8, 8, 5, 1, 7, 7 };
            MergeSort merge = new MergeSort();
            InsertionSort insertion = new InsertionSort();
            ShellSort shell = new ShellSort();
            SelectionSort selection = new SelectionSort();
            QuickSort 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));
        }

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

另请参阅

SortApplication 库

上一题 下一题