2.1.11

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

解答

希尔排序的官方实现:https://algs4.cs.princeton.edu/21elementary/Shell.java.html
只要稍作修改即可,详情见代码。

代码

/// <summary>
/// 利用希尔排序将数组按升序排序。
/// </summary>
/// <param name="a">需要排序的数组。</param>
public override void Sort<T>(T[] a)
{
    int n = a.Length;
    int[] h = new int[2];   // 预先准备好的 h 值数组

    int hTemp = 1;
    int sequenceSize = 0;
    for (sequenceSize = 0; hTemp < n; sequenceSize++)
    {
        if (sequenceSize >= h.Length)  // 如果数组不够大则双倍扩容
        {
            int[] expand = new int[h.Length * 2];
            for (int j = 0; j < h.Length; j++)
            {
                expand[j] = h[j];
            }
            h = expand;
        }
        h[sequenceSize] = hTemp;
        hTemp = hTemp * 3 + 1;
    }

    for (int t = sequenceSize - 1; t >= 0; t--)
    {
        for (int i = h[t]; i < n; i++)
        {
            for (int j = i; j >= h[t] && Less(a[j], a[j - h[t]]); j -= h[t])
            {
                Exch(a, j, j - h[t]);
            }
        }
        Debug.Assert(IsHSorted(a, h[t]));
    }
    Debug.Assert(IsSorted(a));
}

另请参阅

Sort 库

上一题 下一题