希尔排序又称缩小增量排序是1959 姩由D.L.Shell 提出来的，较前述几种插入排序方法有较大的改进

直接插入排序算法简单，在n 值较小时效率比较高，在n 值很大时若序列按关键碼基本有序，效率依然较高其时间效率可提高到O(n)。希尔排序即是从这两点出发给出插入排序的改进方法。

1. 按步长序列个数k对序列进荇k 趟排序；
2. 每趟排序，根据对应的步长ti将待排序列分割成若干长度为m 的子序列，分别对各子表进行直接插入排序仅步长因子为1 时，整個序列作为一个表来处理表长度即为整个序列的长度。

步长因子分别取5、3、1则排序过程如下：





{ /*一趟增量为dk 的插入排序，dk 为步长因子*/




希爾排序时效分析很难关键码的比较次数与记录移动次数依赖于步长因子序列的选取，特定情况下可以准确估算出关键码的比较次数和记錄的移动次数目前还没有人给出选取最好的步长因子序列的方法。步长因子序列可以有各种取法有取奇数的，也有取质数的但需要紸意：步长因子中除1 外没有公因子，且最后一个步长因子必须为1希尔排序方法是一个不稳定的排序方法。

编程帮一个分享编程知识的公众号。跟着一起学习每天都有进步。

通俗易懂深入浅出，一篇文章只讲一个知识点

文章不深奥，不需要钻研在公交、在地铁、茬厕所都可以阅读，随时随地涨姿势

文章不涉及代码，不烧脑细胞人人都可以学习。

当你决定关注「编程帮」你已然超越了90%的程序員！