希尔排序是对直接插入排序的优化，在学习之前，没有学过插入排序的童鞋们建议先学习插入排序：点击跳转到插入排序
我们发现，当被排序的对象越接近有序时，插入排序的效率越高，那我们是否有办法将数组变成接近有序后再用插入排序，此时希尔大佬就发现了这个排序算法，并命名为希尔排序
希尔排序是对插入排序的优化，基本思路是先选定一个整数作为增量，把待排序文件中的所有数据分组，以每个距离的等差数列为一组，对每一组进行排序，然后将增量缩小，继续分组排序，重复上述动作，直到增量缩小为1时，排序完正好有序。
希尔排序原理是每一对分组进行排序后，整个数据就会更接近有序，当增量缩小为1时，就是插入排序，但是现在的数组非常接近有序，移动的数据很少，所以效率非常高，所以希尔排序又叫缩小增量排序。
每次排序让数组接近有序的过程叫做预排序，最后一次插入是直接插入排序
每一次排序之后数组就会变得接近有序，插入排序的移动次数就会越来越少，效率也不是普通的插入排序能比的了
希尔排序移动次数：共移动8步
综上所述：希尔排序在越大的数组上更能发挥优势，因为步子迈的更大，减少插入排序的移动次数更多
最初希尔提出的增量是gap=n/2，每一次排序完让增量减少一半gap=gap/2，直到gap=1时排序变成了直接插入排序。直到后来Knuth提出的gap=[gap/3]+1，每次排序让增量成为原来的三分之一，加一是防止gap<=3时gap=gap/3=0的发生，导致希尔增量最后不为1，无法完成插入排序。到目前为止业内对于两个大佬的方法依然是看法不一，都没有比出个上下来
我们目前使用的则是Knuth提出的除三法获得希尔增量来演示
希尔排序的代码实现比较魔幻，由于我们讲解的希尔排序的思路是将分组进行直接插入排序，就导致我们容易产生疑惑，是不是分多少组就调用多少次插入排序的代码呢，那这代码量不就随着增量的变化而变化了，但是动态代码这个概念听着就让人倍感稀奇。所以我们仅用一次遍历数组的方式就巧妙对每个分组完成单趟排序，不需要对代码做那样鬼畜的操作
这个过程相当于对每个分组按照一个固定顺序轮流插入排序，并且它们是以一个元素为单位同时进行的，而不是先将某个分组插入排序完再下一个分组。