插入排序

插入排序（Insertion Sort）:工作原理是通过构建有序序列，对于未排序数据，再已排序序列中从后向前扫描，找到对应位置并插入。插入排序再实现上，再从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。

# -*- coding: utf-8 -*-
"""
alist=[93,  54,77,31,44,55,226]
1)将93作为一个有序序列
2）拿后面无序序列和前面有序序列做比较
alist=[54，93,   ,77,31,44,55,226]
"""


def insert_sort(alist):
    n = len(alist)
    # 从右边的无序序列中取出多少个元素执行这样的过程
    for j in range(1, n):
        # j =[1,2,3,n-3]
        # i 代表内层循环起始值
        i=j
        # 执行从右边的无序序列中取出第一个元素，即i位置的元素，然后将其插入到前的正确位置中
        while i>0:
            if alist[i]<alist[i-1]:
                alist[i],alist[i-1]=alist[i-1],alist[i]
                i-=1
            else:
                break
if __name__ == '__main__':
    li = [54,26,93,17,77,31,44,55,20]
    print(li)
    insert_sort(li)
    print(li)