# 插入排序（英语：Insertion Sort）是一种简单直观的排序算法。
# 它的工作原理是通过构建有序序列，对于未排序数据，
# 在已排序序列中从后向前扫描，找到相应位置并插入。
# 插入排序在实现上，在从后向前扫描过程中，
# 需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。

个人理解，从头到尾，拿第n个元素跟第n-1个元素对比，如果第n个大于（或小于）第n-1个元素，则需要进行数据交换，

外部循环需要执行n-1次，内部循环也需要执行n次，如果列表越长，越到后面执行效率越低。

mublist=[22,89,78,66,15,29,87,55,43]
def insertion_sort(list):
    # 从第二个元素开始 需要遍历n-1次
    for i in range(1,len(list)):
        # 如果第n个元素比n-1个元素小 一一交换
        for j in range(i,0,-1):
            if list[j]<list[j-1]:
                list[j],list[j-1]=list[j-1],list[j]


insertion_sort(mublist)
print(mublist)

执行效果 [15, 22, 29, 43, 55, 66, 78, 87, 89]