Shell排序又叫缩小增量排序(diminishing increment sort).
Shell排序是一种不稳定的排序算法，其时间复杂度受增量序列的影响非常大，最坏的情况是o(n^2)。Shell排序常用的增量序
列(H1必须为1)有:
Shell最初建议步长选择为n/2，并且对步长取半直到步长达到1
Knuth序列Hn = 3 * Hn-1 + 1
Hibbard序列1, 3, ..., 2^k - 1
Shell排序的一个重要性质是, 一个Hk-排序的文件(以后将是Hk-1-排序)保持它的Hk-排序性. 事实上,假如情况不是这样的话, 那
么该算法也就没有什么意义了. 因为前面各趟排序的结果就会被后面各趟排序给打乱.
一趟Hk-排序的作用就是对Hk个独立的子数组执行一次插入排序.
Shell排序的算法实现我放在这里.
Reference:
Shell排序: http://blog.csdn.net/gulianchao/article/details/8581210