希尔排序（Shell’s Sort）又称“缩小增量排序”，它也是插入排序的一种，但时间效率上较直接插入排序有较大的改进。

希尔排序是对直接插入排序算法的一种改进，对直接插入排序算法分析，其时间复杂度为O(n2)，若待排序序列正序的时候时间复杂度为O(n)，由此可知，待排序序列基本有序时其效率高。 从另一方面看，直接插入排序算法简单，若待排序序列元素少时，也不需要进行大量的移动和比较，因此其效率也高。

①先将整个待排序序列分割成若干个子序列，②然后分别进行【直接插入排序】，③然后缩小增量，在执行①②步，直到缩小至1，再执行④ ④待整个序列中的记录“基本有序”再对整个序列进行一次直接插入排序。

算法的思想的目的就是为了让序列元素减少或者基本有序，这样就可以发挥直接插入排序的最高效率。

有个待排序序列为：【4,10,34,54,12,3,1,55,15,13】，需要对此序列进行希尔排序。 算法思想中第一步： 将整个待排序序列分成若干个子序列。对于初学者来说一般想分割序列的方式就是平均分成若干个序列，例如：1-5为一个序列，6-10为第二个序列。 希尔排序采取的是相隔某个“增量”的记录组成的子序列。例如：增量为5，则第1个元素和第6个元素为一个子序列，第2个元素和第7个元素为一个子序列，等等。如图：相同颜色为一个子序列。

算法思想中第二步： 然后分别分割后的五个子序列进行直接插入排序。 此时原始序列为：

注意：在很多文章中讲解的是对子序列以次进行直接插入排序，但是我在代码实现过程中发现，这个过程并不是一个子序列全部完成排序后再进行下一个子序列的排序，而是以元素为基准，第一个序列第一个元素，第二个序列第一个元素，第三个序列第一个元素；第一个序列第二个元素，第二个序列第二个元素，第三个序列第二个元素

算法思想中第三步： 缩小增量为：2。 执行算法思想第一步： 分割成若干子序列 执行算法思想第二步： 对每个子序列进行直接插入排序 此时原始序列为： 算法思想中第四步： 此时增量为：1 ，原始序列基本有序，直接对该序列进行直接插入排序即可。

小结：算法思想为四步，只要我们记住这四步就可以理解希尔排序的思想，至于实例讲解和代码实现是为了加深对希尔排序的理解。

希尔排序的时间复杂度介于O(n1.3) 和O(n2)之间，取决于，增量的选取，但至今仍没有一种最好的选取增量的方法。 需注意的是，应使增量没有除1之外的公因子，而且增量最后必须等于1。

O(1)

不稳定的排序