希尔排序（Shell Sort）是一种插入排序算法，因D.L.Shell于1959年提出而得名。
Shell排序又称作缩小增量排序。
希尔排序的中心思想就是：将数据进行分组，然后对每一组数据进行排序，在每一组数据都有序之后
，就可以对所有的分组利用插入排序进行最后一次排序。这样可以显著减少交换的次数，以达到加快排序速度的目的。
希尔排序的中心思想：先取一个小于n的整数d1作为第一个增量，把文件的全部记录分成d1个组。所有距离为dl的倍数的记录放在同一个组中。先在各组内进行直接插人排序；然后，取第二个增量d2<d1重复上述的分组和排序，直至所取的增量dt=1(dt<dt-l<…<d2<d1)，即所有记录放在同一组中进行直接插入排序为止。
该方法实质上是一种分组插入方法。
shell排序的算法实现:
注意：
当增量d=1时，ShellPass和InsertSort基本一致，只是由于没有哨兵而在内循环中增加了一个循环判定条件"j>0"，以防下标越界。
1、增量序列的选择。
Shell排序的执行时间依赖于增量序列。好的增量序列的共同特征如下：
a.最后一个增量必须为1。
b.应该尽量避免序列中的值(尤其是相邻的值)互为倍数的情况。
有人通过大量实验给出了目前最好的结果：当n较大时，比较和移动的次数大概在n^1.25到n^1.26之间。
2、Shell排序的时间性能优于直接插入排序。
希尔排序的时间性能优于直接排序的原因如下：
a.当文件初态基本有序时，直接插入排序所需的比较和移动次数均较少。
b.当n值较小时，n和n^2的差别也较小，即直接插入排序的最好时间复杂度O(n)和最坏时间复杂度O(n^2)差别不大。
c.在希尔排序开始时增量较大，分组较多，每组记录数目少，故每组内直接插入排序较快，后来增量d(i)逐渐缩小，分组数逐渐减少，而各组的记录数目逐渐增多，但由于已经按d(i-1)做为距离拍过序，使文件较接近于有序状态，所以新的一趟排序过程也较快。因此，希尔排序在效率上较直接插入排序有较大的改进。
3、稳定性
希尔排序是不稳定的。
假定待排序文件由10个记录，其关键字分别是：40、38、65、97、76、13、27、49、55、04。
增量序列取值依次为：5、3、1
排序过程演示如下图所示：
其动画效果如下面的gif动画所示：
ps:读者也可以自己打开下面的链接，自己设定要排序的数组，进行排序演练
运行结果为：
发现增长序列是5,2,1 和题目要求的5,3,1不同。通过分析要排序的文件由10个记录，10/2=5,5-2=3,3-2=1。刚好符合要求，因此将上面的代码稍作修改即可改变增长序列的值。
将shellSort(int[] source) 方法里的下面这行代码
改为：
然后重新运行程序，打印结果如下：
=================================================================
如果想使用指定的增长序列来对指定的数组进行希尔排序，可以对上面的程序修改，修改后代码如下：
运行结果如下：
==============================================================================================
作者：欧阳鹏 欢迎转载，与人分享是进步的源泉！