在跟我学算法（四）——简单的插入排序一节中我们共同学习了插入排序算法，插入算法主要就是比较和移动两个操作，造成了时间复杂度大的问题。但是插入算法在序列本身有序时能达到O(N)的时间复杂度，也就是说实际上如果序列本身有一定的有序性，那么效率也会更高。而且如果序列本身很短的话，插入排序的效率很是很好的。
希尔排序算法就是在插入排序算法的基础上改进产生的。
希尔排序的基本思想是：把序列按照一定的增量分割成多个子序列。而这个子序列不是连续的，而是通过前面提到的增量，按照一定相隔的增量进行分割的，然后对各个子序列进行插入排序，然后增量逐渐减小，最终减小到1即直接使用插入排序处理序列。
这里增量的选择要求每次都要减少，直至最后一次变为1为止。
上面那样子描述可能让我们很难理解，我们这里再来举个例子。
这里我们采用首选增量为n/2，并且每次选择的增量都为前一次的1/2 。
初始序列：592、401、874、141、348、72、911、887、820、283 。
这里有10个数，我们按照上面说的首选增量设置为10/2即5，那么做如下处理：
这里解释一下：我们的增量是5，所以我们选择第一组序列的时候选择第一个和第六个，第二组序列自然是第二个和第七个，以此类推。分别选出5组序列，每组序列两个数，用直接插入排序算法排序。
这里72需要插入到592的前面，也就是第一组数变为72、592，第二组数不变，第三组数不变，第四组同样不变，第五组数需要变为283、348 。这时候我们的数组就变成了图中显示的结果，即72、401、874、141、283、592、911、887、820、348 。这是第一趟排序。
这里特别说明一下，希尔排序用的还是原本的数组，根本上还是在每组序列中使用的插入排序，忘记的同学自己去回顾一下插入排序去。
第二趟增量是5/2=2，所以我们就是做如下分组，总共分了两组，分别进行插入排序，第三趟增量是2/2=1了，于是就是直接的插入排序了。接下来我就直接上图了。
最后我们总结一下，这个希尔排序实际上只是使用了一种增量的方式改进插入排序。不管序列总数有多少，刚开始增量很大，所以每次的插入排序实际上都很块，因为规模很小。尽管在之后规模慢慢变大，但是那时候这个序列已经越来越基本有序了，所以插入排序算法的速度也是越来越好。
在时间复杂度这一点上，由于增量的序列不一定，时间复杂度也不确定。这在数学上还无法给出确切的结果。我们在上面采用的是简单的除2方式，但是据研究，有几种推荐的序列：
1：N/3+1，N/3^2+1，N/3^3+1...（据说在序列数N<10w时最优）
2：2^k-1，2^(k-1)-1，2^(k-2)-1...（设k为总趟数）
大家有兴趣可以试试上述两种方式的增量处理，其实思想都一样，建议第一种方式，比较简单，效率也比较好。
本文原创于本人博客，请访问 http://irfen.me
©原创文章，转载请注明来源： 赵伊凡's Blog
©本文链接地址: 跟我学算法（六）——直接插入的改进希尔排序
能把算法的源码发出来吗？ 源码太少了。
这个系列很不错，有兴趣扩展成书出版吗
很不错的网站，交换友情链接不，最励志网:http://www.zuilizhi.net/?
已加
路过，留个脚印，网站很棒！
不错不错，来看看。。
帅哥，你的博客写的不少，不知道为什么你不用markdown来写，这样格式和分段好好控制
其实是有点懒得弄了，能发发文章先将就下了