通过直接插入排序的修炼，我们知道直接插入排序是一种性能比较低的初级算法，对修炼者提升不是不大， 但是有一点优势那就是对于小型数组或者部分有序的数组非常高效，希尔排序就是基于这一点优势对直接插入排序进行了改良。换句话说直接插入排序低效的原因在于无序，无序的程度越高越低效。例如：最小的元素初始位置在数组的另一端，此元素要想到达正确位置，是需要一个一个位置前移，最终需要N-1次移动。如何改变这种状态正是希尔排序的突破口。
希尔排序的思想是把数组下标按照一定的增量h分组，然后对每组进行直接插入排序。在进行排序时，如果h很大，我们就能将元素移动到很远的地方，为实现更小的h有序创造方便。然后增量h逐渐减小（每个分组的元素量增多），直到h为1整个数组划分为一组，排序结束。
也许一张更直观的图比上千句话效果都好
时间复杂度
最坏时间复杂度依然为O(n²)，一些经过优化的增量序列如Hibbard经过复杂证明可使得最坏时间复杂度为O(n^3/2)，最好情况下为O(n)属于线性复杂度。
空间复杂度
优于希尔排序本质上属于插入排序升级版，所以空间上和直接插入排序一致为O(1)，在常数级别。
希尔排序之所以高效是因为它权衡了子数组的规模和有序性。排序之初各个子数组都很短，这种情况很适合插入排序.
对于增量h的选择对希尔排序非常重要，直接影响其性能。其实除了h的选择之外，h之间的数学性质也影响希尔排序的性能，比如它们的公因子等。很多论文研究了各种不同的递增续列但都无法证明某个序列是最好的。对于某些基础递增的序列其实在性能上和某些复杂的序列接近，所以很多情况下我们没有必要花大力气在复杂序列上的研究上。
适用场景
与插入排序不同，希尔排序可以适用于大型数组，它对任意排序的数组表现良好，虽然不是最好。实验证明，希尔排序比我们上两章学习的选择排序和插入排序要快的多，并且数组越大，优势越大。目前最重要的结论是：希尔排序的运行时间达不到平方级别。
对于中等大小的数组希尔排序的时间是在可接受范围之内的，因为它的代码量很小，而且需要的额外空间很小，几乎可以忽略。对于其他更高效的其他算法，可能比希尔排序更高效，但是代码也更复杂，性能上比希尔排序也高不了几倍，所以在很多情况下希尔排序成为首选的算法。
1. 直接插入排序是稳定的，希尔排序呢？