2.1.19

2.1.19 #

解答 #

不得不说这道题意外的难。

放上论文链接: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

这个序列是:

48, 46, 54, 97, 83, 69, 76, 25, 10, 5, 87, 12, 21, 99, 61, 33, 30, 47, 57, 4, 36, 42, 98, 66, 100, 17, 94, 81, 11, 77, 24, 89, 73, 53, 38, 7, 29, 8, 27, 23, 56, 70, 60, 85, 39, 65, 9, 75, 15, 67, 64, 22, 51, 82, 43, 3, 37, 91, 45, 13, 34, 63, 74, 71, 95, 55, 80, 92, 2, 19, 62, 40, 84, 41, 50, 88, 86, 59, 28, 44, 72, 68, 14, 35, 93, 26, 18, 78, 31, 58, 96, 6, 1, 90, 49, 16, 52, 79, 32, 20

会比较 999 次。

代码 #

构造最坏情况的类

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

        for (var i = 0; i < a.Length; i++)
        {
            a[i] = null;
        }

        var p = 40;
        var pAddition = p;
        while (l < 100)
        {
            for (var j = 1; j <= n; j++)
            {
                if (a[j] == null && IsVisible(j, p))
                {
                    l++;
                    a[j] = l;
                }
            }

            p += pAddition;
        }

        var b = new int[n];
        for (var 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)
    {
        var k = 0;
        while (k <= 100)
        {
            if (j - i >= k * 40 && j - i <= k * 41)
                return true;
            k++;
        }

        return false;
    }
}

会显示比较次数的 ShellSort 类

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

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

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

    private bool LessAndCount<T>(T a, T b, ref int count) where T : IComparable<T>
    {
        count++;
        return Less(a, b);
    }

    /// <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 (var i = h; i < a.Length; i++)
        {
            if (Less(a[i], a[i - h]))
            {
                return false;
            }
        }
        return true;
    }
}

main 方法

// 开放题,没有标准答案
// 共参考的最差情况为 n^(3/2)
// 本例共 761 次
int[] b;
var sort = new ShellSort();
b = ShellSortWorstCase.GetWorst(100);
for (var i = 0; i < b.Length; i++)
{
    Console.Write(b[i] + " ");
}

Console.WriteLine();
sort.Sort(b);

另请参阅 #

Sort 库