果然能用名字来命名的知识都是大神级别的。最近学习了希尔排序，写一篇文章总结一下，相信你看了会有很大收获。
声明一点本处的增量选择采用的是希尔建议的方式，而更好的方式是采用互质的增量序列。选择这样的目的是不增加代码的复杂性，从而更好的理解希尔排序。一旦我们理解了基本原理，其余的都是很好解决的，一起来看看。
- 一.前言
- 二.思想及操作
- 三.代码设计
- 四.代码实现
- 五.代码解读
- 六.希尔排序总结
一.前言
我们都知道插入排序按查找位置的方式不同，又可以分为三类：采用顺序法查找插入位置——直接插入排序；采用折半（二分）查找法查找插入位置——折半（二分）插入排序；缩小增量多遍插入排序——希尔排序。
同时插入排序的效率是由比较次数和移动次数共同决定的。
直接插入排序：
如果原始数据越接近有序，直接插入排序效率较高（即逆序个数越少越快）；在待排序的记录个数较少时，效率较高。直接插入排序是一种稳定的插入排序
折半插入排序：
该方法相对直接插入排序，降低 了比较的次数，但是没有降低移动的次数。平均性能来说比直接插入排序要好。该方法也是一种稳定的插入排序。
那么有没有一种方式即能降低比较次数又能降低移动次数，答案就是希尔排序。
希尔排序也称为缩小增量排序。增量指的是按照某一种约定对数据进行分组，比如将数据5个5个的分为一组。缩小增量也就指按某种约定将分组的范围缩小，直到增量为1。
二.思想及操作
基本思想：
先将整个待排记录序列分割成若干子序列，分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行一次直接插入排序。
希尔排序图解：
有如上所示图，第一排为数组下标，第二排代表每个数组位置所对应存储的数据，现在要从小到大对该数据进行排序。我们按照希尔排序的发明者Donald Shell所建议的选择增量序列的方式：初始增量为数据个数的一半，之后的每一次都变为二分之一，直到增量变为1。
第一次按增量为6（13/2=6）进行分组,下图中颜色一样的代表将会分为一组，如下：
分组完成如下：
分组完成后各组内进行排序，即采用直接插入排序对各组内成员进行排序，如下：
此时我们发现颜色相同的组都已经按照从小到大进行排序了，去掉颜色如下：
第二次按增量为6/2=3进行分组,颜色一样的同样代表分为一组，如下：
分组完成后各组内进行排序，如下：
同样颜色相同的组都已经按照从小到大进行排序了，去掉颜色如下：
此时数据大部分已经变为有序。下一步操作执行增量为3/2=1的操作，这就是我们所熟悉的直接插入排序，即将所有的数据分为一组，进行直接插入排序，给出排序后的结果如下：
通过这样的方式使排序的移动次数和比较次数都得到减少，从而使得算法效率得到提高。
我相信大家都有这样的感觉就是道理都懂，但就是写不出代码，而且看希尔排序的代码也很难理解。希尔排序它的难点就是在与代码逻辑和我们实际的分析逻辑是有出入的。我也是卡了好久才明白过来，继续往下看。
三.代码设计
希尔排序的整体步骤如下：
1.第一次分组。即增量的初始值为数据长度的一半；
2.组内进行排序。即采用直接插入排序对各组进行排序；
3.重新设置间隔分组。即将增量缩小重新进行分组；
4.重复2、3步骤直到增量为1，再对整个数据进行直接插入排序。
通过以上分析，我们发现希尔排序将会存在有三层循环。第一层循环为控制增量的循环；第二层循环为需要依次对各组进行排序的循环。这里所指的意思是第一组后、再第二组、再第三组依次下去；第三层循环为各组内进行排序的循环。
其次我们要记住一个核心点，插入一个元素到数组某一个位置，需要将该位置及后的数据整体后移一个位置，空出该位置才能进行插入。对于希尔排序依旧如此，只是其跨度又原来的一个位置，变为了一大段距离，即增量个位置。
来看看下面的例子：
对于直接插入排序移动数据只能一次移动一个位置，而对于希尔排序此时可以将6号位置减去增量（6-6=0）即移动到0号位置，完成数据交换，跨度变大，对于第一组的排序结束。哎！我们有疑问了，12号位置呢？12号位置还没有比较移动呢！对这就是我们分析逻辑和代码逻辑上的出入。原因呢在于每一组我们都先实现部分排序，通过后面的遍历不断完善每一组的排序。
也就是说希尔排序并不是将数据分组后立即完成对本组所有数据的排序（我们分析是如此进行的），而是对于每一组都先实现部分排序，之后再不断完善对每一组的排序。
先看代码，我们根据代码再作分析。
四.代码实现
typedef int ElementType;
void ShellSort(ElementType array[], int size)
{
int increment;//增量
int temp;//零时变量，用于临时存储数据
int i,j;
for (increment = size / 2; increment > 0; increment /= 2)//初始增量为size/2，每一趟之后除以二
{
for (i = increment; i < size; i++)//依次对每一组进行部分排序，且不断完善每一组的排序
{
temp = array[i];//将数据进行拷贝
for (j = i; j >= increment && temp < array[j - increment]; j -= increment)//组内进行排序
{
array[j] = array[j - increment];
}
array[j] = temp;
}
}
}
五.代码解读
我们前文也提及到希尔排序有三层循环：
第一层循环： for (increment = size / 2; increment > 0; increment /= 2) 解读： 本层循环为控制增量的循环，增量初始值为数据元素个数的一半，之后变为原来的二分之一；增量必须是大于零的。
第二层循环：for (i = increment; i < size; i++) 解读： 本层循环依次对各组进行部分排序（第一组之后第二组依次下去），并不断完善。初始值为每组的第二个元素，因为第一个元素本身是有序的。
第三层循环： for (j = i; j >= increment && temp < array[j - increment]; j -= increment) 解读： 本层循环完成对组内的排序，可能是本组部分排序，也有可能是整个组的排序，跨度为增量。
提到希尔排序的代码，我们首先就应该想到它的三层循环，明白每一层循环的含义及作用。而对于循环内部的代码细节和直接插入排序是类似的，只是由原来的一个跨度位置变为了一大段跨度。
六.希尔排序总结
希尔排序特点：
1.每一趟移动，移动位置较大，跳跃式地接近排序后的最终位置；
2.最后一次只需要进行少量移动；
3.增量序列必须是递减的，最后一个必须是1（对整体进行直接插入排序）；
4.增量序列应该是互质的。我们这里选择的是Shell建议的增量选择，即每次变为原来的一半（不是很好）
5.希尔排序是一种不稳定的排序方法，且不宜在链式存储结构上实现
6.希尔排序通过降低比较次数和移动次数来提高排序的效率
希望对你有帮助，我是老胡，感谢阅读！！❤️ ❤️
