1.2 希尔排序
希尔排序属于插入排序的一种，是直接插入排序的优化，其主要思想是：由于在序列基本有序的情况下，直接插入排序的效率很高，那么，我们引入一个增量incre，把以incre为间隔的元素做一次直接插入排序，使其基本有序；随后，incre慢慢减小，继续做上述直接插入排序，最后incre变成1，退化成直接插入排序，但这时候的序列已经基本有序，排序效率非常高。实际上就是让相对较小的元素跳跃着往前移动。其过程如图所示：
希尔排序的时间、空间复杂度、稳定性以及适用场合如图：
如图所示，希尔排序的性能在四个改进算法中算不上好（在O(nlgn)~O(n^2)之间，其它3个的平均时间复杂度都为O(nlgn)），但希尔排序的意义在于突破了O(n^2)的限制，为后来更优秀算法打开了思路。