希尔排序的思想是基于直接插入排序提出的。 在直接插入排序时，时间复杂度最好的情况（表中元素已经有序）是 O(n) , 最坏的情况（表中元素刚好逆序）是 O(n^2)。 希尔排序先将间隔 "某个增量d" 的记录组成一个子表，对各个子表进行直接插入排序，随着 “增量d” 逐渐变小，表中元素越来越有序。当 d 变为1时，表中元素已经基本有序，这个时候对全局使用直接插入排序，很快可以得到最终结果。
希尔排序是不稳定的算法！
