主函数迭代次数：数值个数n 0.5n(n + 1)。

"""插入排序
InsertionSort.py"""

# 一次往数组添加多个数字
def AppendNumbers(array):
    num = input('Numbers:(split by spaces)\t').split()
    for i in num:
        array.append(int(i))
    print('排序前数组：{}.'.format(array))

def InsertionSort(array):
    AppendNumbers(array)  # 添加

    list = []
    while True:
        for i in array:
            minimum = min(array)
            if i == minimum:
                list.append(i)
                array.remove(i)  # 删去最小值

        if array == []:
            break

    print('排序后数组：{}.'.format(list))

array = [6, 4, 45, -2, -1, 2, 4, 0, 1, 2, 3, 4, 5, 6, -4, -6,  7, 8, 8, 34, 0]
InsertionSort(array)

参考：

def insertionSort():
    import random
    random.seed(888)
    data=[]
    for i in range(15):
        data.append(random.randint(1, 100))
    print(data)
    for i in range(1,len(data)):
        temp=data[i]
        for j in reversed(range(i)):
            if temp<data[j]:
                data[j+1],data[j]=data[j],temp
    print(data)
insertionSort()

关键在于两组数据，一个是排好的 b，一个是待处理的 a。待处理的（第二个 for）如果小于处理好的，就插入，然后删除原来的。没有替换的关系

l=[2,5,1,4,6,9,3,0,8,7]
for a  in range(1,len(l)):
    for b in range(0,a):
        if l[a]<l[b]:
            l.insert(b,l[a])
            del l[a+1]
            print(l)

输出结果为：

[1, 2, 5, 4, 6, 9, 3, 0, 8, 7]
[1, 2, 4, 5, 6, 9, 3, 0, 8, 7]
[1, 2, 3, 4, 5, 6, 9, 0, 8, 7]
[0, 1, 2, 3, 4, 5, 6, 9, 8, 7]
[0, 1, 2, 3, 4, 5, 6, 8, 9, 7]
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]