2.1.29

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

解答

当然是题目给出的递增序列更快啦,因为这个序列就是作者提出来的嘛。
(论文链接: http://linkinghub.elsevier.com/retrieve/pii/0196677486900015

代码

修改了一下 shellsort,让它按照给定的 h 序列排序。

using System;
using System.Diagnostics;
using Sort;

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

        /// <summary>
        /// 利用希尔排序将数组按升序排序。
        /// </summary>
        /// <typeparam name="T">待排序的元素类型。</typeparam>
        /// <param name="a">待排序的数组。</param>
        /// <param name="h">需要使用的递增序列。</param>
        public void Sort<T>(T[] a, int[] h) where T : IComparable<T>
        {
            int n = a.Length;
            int t = 0;
            while (h[t] < a.Length)
            {
                t++;
                if (t >= h.Length)
                    break;
            }
            t--;

            for ( ; 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));
        }

        /// <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));
        }

        /// <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;
        }
    }
}

另请参阅

Sort 库

上一题 下一题