#插入排序

num = [13,2,8,12,1,456,89]
for i in range(1,len(num)):
    key = num[i]  #获取未排序部分的第一项值
    j = i-1 #设置已排序部分的最后一位编号
    print("需要插入的值：", key)
    while j>=0 and num[j]<key:
        num[j+1] = num[j]
        j -= 1
    print(key,"放在了第",j+1)
    num[j+1] = key
    print(num)
'''
 (n-1)*(n-1)
=n*n - n*1 - 1*n + 1*1
=n*n - 2*n + 1
时间复杂度  O(n^2)
'''