[数据结构与算法]排序算法之希尔排序

? ? ? ? 我想问个问题是这几天的题目比较难？还是比较简单？我看大家没有任何反应，是简单不想做还是代码太难看不懂？大家在群里也没有反馈，哎。

? ? ? ? 我们先讨论上一次的问题。

? ? ? ? 思路是对的，但是在代码实现的时候会遇到一个问题。接下来看图演示

? ? ? ? 红色代表最大值， 绿色代表最小值。

? ? ? ? 此时红色最大值index_max = 1, index_min = 3;

? ? ? ? 第一轮交换之后index_max应该变成了3，但是现在index_max还是1，此时再放到最后的反而是现在在第一个位置的1.有点绕大家看图吧。

? ? ? ? 对应表格中的第二行到第三行

? ? ? ?

? ? ? ? 所以出错了。哎。但是有没有改进方法呢？当然有，但是没有必要，因为改的时候分情况增加了逻辑复杂度，没必要。有兴趣的小伙伴可以留下自己的思考。

? ? ? ? 接下来我们聊一下希尔排序（shell sort）。首先声明：上难度了，有思考的难度但是也不是很大。大家看个shell sort的视频。

????????

作者：Promise_Sun
链接：https://www.jianshu.com/p/d730ae586cf3

希尔排序是基于直接插入排序（可以回顾《排序算法之冒泡排序（一）》）的以下两点性质而提出的改进方法：
1.插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率。
2.插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位。

二、原理

希尔排序是将待排序的数组元素 按下标的一定增量分组 ，分成多个子序列，然后对各个子序列进行直接插入排序算法排序；然后依次缩减增量再进行排序，直到增量为1时，进行最后一次直接插入排序，排序结束。

**增量d 的范围： **1<= d < 待排序数组的长度 （d 需为 int 值）
**增量的取值： **一般的初次取序列（数组）的一半为增量，以后每次减半，直到增量为1。
第一个增量=数组的长度/2,
第二个增量= 第一个增量/2,
第三个增量=第二个增量/2,
以此类推，最后一个增量=1。

好的增量序列的共同特征：
① 最后一个增量必须为1；
② 应该尽量避免序列中的值(尤其是相邻的值)互为倍数的情况。

三、原理过程图解