希尔排序

def insertSort(li):

    for i in range(1,len(li)): #i 表示摸到的牌的下标，注意循环从 1 开始，因为手里的牌是 0

        tmp=li[i]

        j=i-1 #j 表示手里的牌的下标

        while j>=0 and li[j]>tmp: #如果手里的牌比 tmp 小或者手里已经没有牌了，结束循环

            li[j+1]=li[j]

            j-=1

        li[j+1]=tmp

def insertSort_gap(li,gap):

    for i in range(gap,len(li)): #i 表示摸到的牌的下标，注意循环从 gap 开始，因为手里的牌是 0~(gap-1)

        tmp=li[i]

        j=i-gap #j 表示手里的牌的下标

        while j>=0 and li[j]>tmp: #如果手里的牌比 tmp 小或者手里已经没有牌了，结束循环

            li[j+gap]=li[j]

            j-=gap

        li[j+gap]=tmp

def shell_sort(li):

    d=len(li)//2

    while d>=1:

        insertSort_gap(li,d)

        d//=2

# 验证

import random

li=list(range(10))

random.shuffle(li)

print(li)

shell_sort(li)

print(li)