希尔排序

先上代码：

def shellSort(target):
    step = len(target) // 2
    while step > 0:
        # 插入排序代码
        ###
        for j in range(step, len(target)):
            key = target[j]
            i = j - step
            while i >= 0 and target[i] > key:
                target[i+step] = target[i]
                i -= step
            target[i+step] = key
        ###
        # 插入排序代码结束
        step //= 2
    return target

接下来讲解为什么这么写！

1. 首先将数组从中间分开，然后从第二部分开始遍历，调用插入排序，分别将部分每一个元素插入到正确位置。

2. 接着在将数组分成四份，从第二部分开始一直到最后，调用插入排序，将该部分元素分别插入到正确位置。

3. 重复。。。

4. 最后一次直接变成1，对最后一个元素进行插入排序，将其插入到正确位置。。。

看中间部分插入排序代码：将 step 换成 1, 其它位置均不用动，直接变为插入排序代码！！！