‘‘‘
通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，
找到相应位置并插入。插入排序在实现上，在从后向前扫描过程中，
需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。
‘‘‘
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
原文：https://www.cnblogs.com/hany-postq473111315/p/12845283.html