希尔排序是插入排序的一种，是直接插入排序的改进版本。

对于上节介绍的直接插入排序法，如果数据原来就已经按要求的顺序排列，则在排序过程中不需要进行数据移动操作，即可得到有序数列。但是，如果最初的数据是按倒序排列的，则在进行插入排序时每次的比较都需要向后移动数据，这样，将导致算法的效率很低。

希尔排序的思想是把数列划分为若干个较小的数列，对每组数列使用直接插入排序算法排序，随着增量逐渐减少，每组包含的数字越来越多，当增量减至1时，整个数列恰被分成一组，最后再使用一次直接插入排序对整个数列进行排序。

例如有4, 3, 6, 2, 7, 1, 5, 8八个数字，第一次分成四组，即8/2组。如下图，相同颜色的数字为一组，下标为x的数字和下标为x+4的数字为一组。

对这四个数组分别做直接插入排序，即两两比较，如果大的在前则交换位置，得到：

然后缩小组数，4/2=2，缩小为两组。如下图：

对这两个数组分别做直接插入排序，得到：

再次缩小组数，2/2=1，缩小为一组，那么所有数字都。如下图：

最后，对4, 1, 5, 2, 6, 3, 7, 8这个数列执行一次直接插入排序。

总结上面的规律，可以得出：

第一次分组数s = n / 2 == 0 ? n / 2 : n / 2 + 1

取数规则是[x]和[x+n/2]为一组

当然，这只是比较简单的分组方式，不一定是最优的。来看代码：

运行：

希尔排序的时间复杂度，最坏是O(n^2)，平均O(n^3/2)。