数据结构之希尔排序

希尔排序

在插入排序的基础上，进行完善的算法

举个例子

如图我们把相距举例为4的两个元素组成一个子表
（1和5，2和6，3和7，4和8）
对各个子表进行直接插入排序

比如对子表2进行直接插入排序
13插入到38前，子表3，4也是
第一趟处理完
然后进行第二趟，会缩小增量d
这里是直接除2，d=2
1 3 5 7变为一组

第二趟结果

其实上面的操作实现了基本有序的状态
最后d=1就和直接插入排序没什么区别了，整个表都是子表呗

希尔排序其实d怎么变都可以，只要递减到1即可
建议是除2

常考考法

告诉你序列和每一趟增量让你求对应的直接插入排序完的序列

算法实现

算法性能分析

直接d=1（那不就是直接插入排序）时候就是O(n^2)
一个范围内就是O(n^1.3)