希尔排序

算法定义

希尔排序，又称缩小增量排序，不要被这个名字吓到，其实，它只是对插入算法的改进而已。

当待排序列基本有序的情况下，插入算法的效率非常高，那么希尔排序就是利用这个特点对插入算法进行了改造升级

分组

待排序数组为

4,1,67,34,12,35,14,8,6,19

第一轮希尔排序

希尔排序的关键在于对待排序列进行分组，这个分组并不是真的对序列进行了拆分，而仅仅是虚拟的分组

首先，用10/2 = 5, 这里的5就是缩小增量排序中的那个“增量”。从第0个元素开始，每个元素都与自己距离为5的元素分为一组，那么这样一来分组情况就是

4   35
1   14
67  8
34  6
12  19

需要注意的是，所谓的分组，仅仅是逻辑上的分组，这10个元素仍然在原来的序列中。上面一共分了5组，每一组都进行插入排序，67 和 8 交换位置，34 和6 交换位置，这样第一次分组后并对各组进行插入排序后，序列变成了

4, 1, 8, 6, 12, 35, 14, 67, 34, 19

第二轮希尔排序

上一轮排序时，增量为5，那么这一轮增量为5/2 = 2，这就意味着，从第0个元素开始，每个元素都与自己距离为2的元素分为一组，分组情况如下

4 8 12 14 34
1 6 35 67 19

整个序列被分成了两组，分别对他们进行插入排序，排序后的结果为

4, 1, 8, 6, 12, 19, 14, 35, 34, 67

第三轮希尔排序

上一轮排序时，增量为2，这一轮增量为2 /2 = 1，当增量为1的时候，其实就只能分出一个组了，这样，就完全的退化成插入排序了，但是，由于已经进行了两轮希尔排序，使得序列已经基本有序了，那么此时进行插入排序，效果就会非常好

增量从5变为2，从2变为1，是逐渐减小的过程，增量是分组时所使用的步长。

示例代码

有了前面的概念以及算法的理解，写出代码就变得容易了，先分组，然后进行插入排序，你唯一要注意的地方是进行插入排序时，要弄清楚，哪些元素是一组的

lst = [4,1,67,34,12,35,14,8,6,19]
length = len(lst)
step = length//2

while step > 0:

    for i in range(step):
        # 插入排序
        for j in range(i+step, length, step):
            if lst[j] < lst[j-step]:
                tmp = lst[j]
                k = j-step

                while k >= 0 and lst[k] > tmp:
                    lst[k+step] = lst[k]
                    k -= step

                lst[k+step] = tmp
    step //= 2 #缩小增量

print lst