希尔排序(Shell Sort)，一听这名字就知道是一个叫希尔的外国人发明的排序。没错，他就是唐纳德 希尔（Donald Shell），一位美国的计算机科学家，他于1959年发明的希尔排序算法。
对于希尔排序，比较正式的官方的解释是这样：
希尔排序也是插入排序的一种。既然是其中的一种，那么他们的区别是什么呢？插入排序在最坏的情况下，即整个数组是倒序的，此时时间复杂度达到了O(n 2 )。希尔排序在插入排序的基础上增加一个叫 增量 的概念。那什么增量？插入排序只能与相邻的元素进行比较，而希尔排序则是进行跳跃比较，而增量就是步长。比如增量为3时，下标为0的元素与下标为3的元素比较，3再与6比较，1与4比较，4再与7比较……想必你肯定做过一群人站成一排，按一二报数，喊一的一队，喊二的一队，此时的增量就是2。所以你也可以理解为是按增量进行了分组，再对每一组进行插入排序。当使用一个增量对所有的分组排好序后，再去减少增量，重复之前步骤，直到增量为1，此时只有一个分组了，再对这一个分组进行插入排序，整个希尔排序就结束了（所以希尔排序也叫 缩小增量排序 ，但显然没有希尔排序好听和高大上 斜眼笑）。
从增量的初始值选取，到逐渐变为1，将所有用过的增量组成一个序列，就是 增量序列 。而希尔排序的增量序列选择直接影响它的时间复杂度（不要问我为什么，我也不知道）。最简单的增量就是希尔鼓励使用的希尔增量。增量初始值选择为N/2（N为数组长度），然后每次将增量除以2，得到下一个增量。所以它的增量序列为{N/2, (N / 2)/2, ..., 1}。除了希尔增量还有 Hibbard 增量 、 Knuth增量 等等都是很复杂的数学公式，我怕你看了晕，就放在后面介绍吧！（说的好像自己看了不晕一样）
那下面我们就以最简单的希尔增量来进行希尔排序。
然后对比之前文章所写的选择排序和插入排序。
三个同样的数组，分别使用选择、插入、希尔进行排序比较时间。
数组长度1万时打印结果为：
数组长度为两万时打印结果为：
差距是很明显的。
希尔排序为 不稳定性排序 。因为相同的元素可能在各自的插入排序中移动，所以它的稳定性就被打破了。可能有人想问，稳定性是干嘛的啊？稳定的意思是指 相同的元素在排序后的相对位置不变 。比如有两个5 ，作为区分前面的叫5 1 ，后面的叫5 2 ，排序完成后5 1 还在5 2 的前面。那你可能会问，反正是一样的，换了就换呗。但是在实际应用中被排序的对象会拥有不同的属性，举个栗子，公司在招聘时，想要年龄小的，所以对所有人进行了按年龄的排序。之后还想看成绩分数高的。所以在按成绩进行排序时就有可能出现成绩一样的，但他们的年龄不一样，而你不能把成绩相同但年龄大的排在小的前面。此时算法的稳定性就有了意义。
使用希尔增量，在最坏的情况下时间复杂度仍为O(n 2 ),而使用hibbard增量在最坏的情况下却为O(n 3/2 )。
如果觉得作者对哪里的理解有偏差或者其他的优化，希望不吝赐教，留言指正。谢谢支持~