插入排序

'''
通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，
找到相应位置并插入。插入排序在实现上，在从后向前扫描过程中，
需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。
'''
def insert_sort(lst):
    for i in range(1,len(lst)):
        # 比较的次数
        for j in range(i,0,-1):
            # 需要比较的次数不断增加
            # 需要插入的元素不断增加,i不断变大
            if lst[j] < lst[j-1]:
                lst[j],lst[j-1] = lst[j-1],lst[j]


lst = [54,26,93,17,77,31,44,55,20]
insert_sort(lst)
print(lst)

---

2020-05-07