希尔排序相当于直接插入排序的升级(分组插入排序)，又称缩小增量排序，同属于插入排序类，不是稳定的排序算法。
比直接插入排序快的原因：

1. 刚开始的时候间隔较大， 每个组里面的数据较少，排序很快；
2. 当分隔加大的时候， 每组的数据变多， 但是因为已经有了前面的工作，数据接近于有序， 所以也很快

基本思想：先将整个待排元素序列分割成若干个子序列（由相隔某个“增量”的元素组成的）分别进行直接插入排序，然后依次缩减增量再进行排序，待整个序列中的元素基本有序（增量足够小）时，再对全体元素进行一次直接插入排序。因为直接插入排序在元素基本有序的情况下，效率是很高的，因此希尔排序在时间效率上比前两种方法有较大提高。 Continue reading →