数据结构与算法（二十一）

谢尔排序：

插入排序回顾：

#插入排序算法：
def  insertSort(alist):
    for index in range(1,len(alist)):
        
        currentvalue = alist[index]
        position = index
        
        while position > 0 and alist[position-1] >  currentvalue:
            alist[position] = alist[position-1]#将比它大的后移
            position = position - 1
            
        alist[position] = currentvalue

巨人的肩膀！：

https://sunzhaoxiang.blog.csdn.net/article/details/80006224

代码实现：

b = len(a)                         #列表长度
gap = b // 2                       #初始步长设置为总长度的一半
while gap >= 1:
    for i in range (b):
        j = i
        while j>=gap and a[j-gap] > a[j]:   #在每一组里面进行直接插入排序
            a[j],a[j-gap] = a[j-gap],a[j]
            j-= gap
    gap=gap//2                              #更新步长