【数据结构】希尔排序(最小增量排序)

👦个人主页：Weraphael
✍🏻作者简介：目前正在学习c++和算法
✈️专栏：数据结构
🐋 希望大家多多支持，咱一起进步！😁
如果文章有啥瑕疵
希望大佬指点一二
如果文章对你有帮助的话
欢迎 评论💬 点赞👍🏻 收藏 📂 加关注😍

一、希尔排序的由来

• 从直接插入排序中，我们总结了：(假定要求升序)当原数组是逆序的时候，时间复杂度为O(N²)，效率极低。博客地址：点击跳转
• 当原数组是接近升序或者已经是有序的，那么时间复杂度就是O(N)，此时效率最高。

因此，又一位名叫希尔的大佬发现，如果一开始就让数组内的元素接近有序的话，那插入排序的效率不就大大提升了吗？所以，希尔排序是插入排序的优化。

二、算法思路

1. 预排序 — 首先让序列中的元素接近有序。

那么如何进行预排序呢？（重点）

其运用了 分组插排 的思想：定义一个变量gap，间隔为gap分为一组进行插入排序

2. 最后再对数组进行插入排序即可。

【画图演示】

通过以上图片，我们还可以总结一个规律：gap为几，就代表预排序有几组

接下来我们简单实现预排序的代码。

三、预排序代码实现

void ShellSort(int a[], int n)
{
    // 假设gap为3
    int gap = 3;
    // 1. gap是几，就代表有几组
    for (int i = 0; i < gap; i++)
    {
        // 2. 间隔为gap为一组进行插入排序
        for (int j = i; j < n - gap; j += gap)
        {
        	// 下面基本都是插入排序的代码(类似)
            int end = j;
            int temp = a[j + gap];
            while (end >= 0)
            {
                if (temp < a[end])
                {
                    a[end + gap] = a[end];
                    end -= gap;
                }
                else
                {
                    a[end + gap] = temp;
                }
            }
            a[end + gap] = temp;
        }
    }
}

那么最后就要对整体进行插入排序，这样就能完美实现希尔排序了。但是我们难道还要重新再其后再手搓一个插入排序吗？理论上是可以的，但是没必要。注意看：当间隔gap为1时，不就是插入排序了吗？因此，普通插入排序和gap是有关系的。那么应该如何选择gap呢？

四、如何选择gap

gap越大，跳的越快，越不接近有序；gap越小，跳的越慢，越接近有序。

可以为大家验证一下：

• 当gap = 3时

是不是越接近有序！

• 当gap = 5时

虽然也接近有序，但是没有比gap = 3更接近有序！

那么gap到底取多少合适呢？

解答：gap应该要不断在变化。为什么呢？开头的结论：gap越大，跳的越快，越不接近有序；gap越小，跳的越慢，越接近有序。如果gap是固定大小，给大了越不接近有序，给小了接近有序，但是跳的慢。因此，预排序的为了让更大的数更快的跳到后面，越小数越快跳到前面。这就是为什么gap应该要不断的变化。

• 最初希尔大佬提出取gap /= 2，为什么呢？因为一个数不断/2，最后的结果一定为1，那么在上面我们说过，当gap = 1，就可以满足整体的插入排序，就不需要再手搓普通插入排序了。

• 后来Knuth提出取gap = gap / 3 + 1（+1为了保证最后gap一定为1），还有人提出取奇数好，也有人提出gap互质好。但无论哪一种主张都没有得到证明。其实都是ok的

五、代码实现(完整版)

void ShellSort(int a[], int n)
{
	// 3. 如何取gap
    // gap最大可以取到整个数组的长度n
    int gap = n;
    while (gap > 1)
    {
        // gap = gap / 3 + 1; // 这也是okk的
        gap /= 2;
        //  1. gap是几，就代表有几组
        for (int i = 0; i < gap; i++)
        {
            // 2. 间隔为gap为一组进行插入排序
            for (int j = i; j < n - gap; j += gap)
            {
                int end = j;
                int temp = a[j + gap];
                while (end >= 0)
                {
                    if (temp < a[end])
                    {
                        a[end + gap] = a[end];
                        end -= gap;
                    }
                    else
                    {
                        break;
                    }
                }
                a[end + gap] = temp;
            }
        }
    }
}

【结果展示】

六、性能分析

• 时间复杂度

希尔排序的时间复杂度不好计算，因为gap的取值方法很多，导致很难去计算。Knuth大佬进行了大量的试验统计，计算出希尔排序的时间复杂度大约为O(N^1.3)

但是我们可以用代码进行性能测试的对比

如图，当数据个数是10w时，插入排序和希尔排序时间效率如下所示

由此看出，希尔排序还是非常的牛逼的~

• 有人想：希尔排序在预排序的时候不是运用到很多的插入排序，为什么其效率还是比插入排序高？

原因是：其实gap的取值决定数组内的元素是否接近有序，gap越大，排的也越快，但越不接近有序；gap越小，排的也就越慢，但越接近有序。所以一开始gap的值可以设为数组元素个数（gap一定不可能超过数组元素个数），每次进行/2，不断缩小gap，其实最后发现，希尔排序的插入排序的次数其实是小于直接排序的插入次数的。