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 库