排序-希尔排序

    希尔排序也叫缩减增量排序，希尔排序是对插入排序的优化，第一次以间隔一定gap将数组分为多个数组，对子数组做插入排序，然后对gap逐级递减，最后gap等于1，gap等于1时候相当于做全量的插入排序，但是又因为将过多次自排序，已经一定程度有序了，无需2层循坏。

    希尔排序对插入排序最重要的优化在于每次移动的时候不只是移动了一个元素。

    希尔排序最难点的是增量序列的算法。

    希尔排序的空间复杂度是O(1)，时间复杂度是O(n) - O($n^2$)，平均复杂度和增量序列有关。

    希尔排序用的比较少，主要是承前启后，给了后面效率比较好的排序一个启发。