2.1.19

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

解答

不得不说这道题意外的难。
放上论文链接:Shellsort and Sorting Networks (Outstanding Dissertations in the Computer Sciences)
这篇论文的第二章给出了一种构造最坏序列的方法,当然理想最坏(n^(3/2))是达不到的了。
最后结果是 793 次。

@杨晗 通过随机输入获得了一个理论最坏的输入序列,见:https://github.com/YangXiaoHei/Algorithms/blob/master/Ch_2_1_Elementary_Sorts/Practise_2_1_19.java

代码

构造最坏情况的类

namespace _2._1._19
{
    class ShellSortWorstCase
    {
        /// <summary>
        /// 获得最坏情况的数组。
        /// </summary>
        /// <param name="n">数组大小。</param>
        /// <returns>希尔排序最坏情况的数组。</returns>
        public static int[] GetWorst(int n)
        {
            int l = 0;
            int?[] a = new int?[n + 1];

            for (int i = 0; i < a.Length; i++)
            {
                a[i] = null;
            }
            int P = 40;
            int PAddition = P;
            for (int i = 0; l < 100; i++)
            {
                for (int j = 1; j <= n; j++)
                {
                    if (a[j] == null && IsVisible(j, P))
                    {
                        l++;
                        a[j] = l;
                    }
                }
                P += PAddition;
            }

            int[] b = new int[n];
            for (int i = 0; i < n; i++)
            {
                b[i] = (int)a[i + 1];
            }

            return b;
        }

        /// <summary>
        /// 确认 j - i 是不是在排序样板(Sorting Template)上。
        /// </summary>
        /// <param name="i"></param>
        /// <param name="j"></param>
        /// <returns></returns>
        public static bool IsVisible(int i, int j)
        {
            int k = 0;
            while (k <= 100)
            {
                if (j - i >= k * 40 && j - i <= k * 41)
                    return true;
                k++;
            }
            return false;
        }
    }
}

会显示比较次数的 ShellSort 类

using System;
using System.Diagnostics;
using Sort;

namespace _2._1._19
{
    public class ShellSort : BaseSort
    {
        /// <summary>
        /// 默认构造函数。
        /// </summary>
        public ShellSort() { }

        /// <summary>
        /// 利用希尔排序将数组按升序排序。
        /// </summary>
        /// <param name="a">需要排序的数组。</param>
        public override void Sort<T>(T[] a)
        {
            int n = a.Length;
            int compareTime = 0;

            int h = 1;
            while (h < n / 3)
            {
                h = 3 * h + 1;
            }

            while (h >= 1)
            {
                for (int i = h; i < n; i++)
                {
                    for (int j = i; j >= h && Less(a[j], a[j - h]); j -= h)
                    {
                        Exch(a, j, j - h);
                        compareTime++;
                    }
                    compareTime++;
                }
                Debug.Assert(IsHSorted(a, h));
                h /= 3;
            }
            Console.WriteLine("CompareTime:" + compareTime);
            Debug.Assert(IsSorted(a));
        }

        /// <summary>
        /// 检查一次希尔排序后的子数组是否有序。
        /// </summary>
        /// <param name="a">排序后的数组。</param>
        /// <param name="h">子数组间隔。</param>
        /// <returns>是否有序。</returns>
        private bool IsHSorted<T>(T[] a, int h) where T : IComparable<T>
        {
            for (int i = h; i < a.Length; i++)
            {
                if (Less(a[i], a[i - h]))
                {
                    return false;
                }
            }
            return true;
        }
    }
}

main 方法

using System;

namespace _2._1._19
{
    /*
     * 2.1.19
     * 
     * 希尔排序的最坏情况。
     * 用 1 到 100 构造一个含有 100 个元素的数组并用希尔排序和
     * 递增序列 1 4 13 40 对其排序,
     * 使比较次数尽可能多。
     * 
     */
    class Program
    {
        // 开放题,没有标准答案
        // 共参考的最差情况为 n^(3/2)
        // 本例共 793 次
        static void Main(string[] args)
        {
            int[] b;
            ShellSort sort = new ShellSort();
            b = ShellSortWorstCase.GetWorst(100);
            for (int i = 0; i < b.Length; i++)
            {
                Console.Write(b[i] + " ");
            }
            Console.WriteLine();
            sort.Sort(b);
        }
    }
}

另请参阅

Sort 库

上一题 下一题