算法之插入排序（python）

def insert_sort(li):
    for i in range(1,len(li)):
        tmp = li[i]    # 记录当前要插入（摸到）的牌
        j = i-1        
        while j>=0 and li[j]>tmp:  # 如果j<0 或者 li[j]的值小于摸到的牌就退出循环
            li[j+1] = li[j]        # li[j]>摸到的牌，li[j]向后移
            j-=1
        li[j+1]=tmp                # 将牌插入

li = [7,4,6,9,5,1,8,2,3]
print(li)
insert_sort(li)
print(li)

1. 这三个排序均是原地排序（即没有多余的列表），在原列表中进行排序。
2. 这三个排序时间时间复杂度均为O(n²)