1.算法：设有一组关键字｛ k 1 ， k 2 ，…， k n ｝；排序开始就认为 k 1 是一个有序序列；让 k 2 插入上述表长为 1 的有序序列，使之成为一个表长为 2 的有序序列；然后让 k 3 插入上述表长为 2 的有序序列，使之成为一个表长为 3 的有序序列；依次类推，最后让 k n 插入上述表长为 n-1 的有序序列，得一个表长为 n 的有序序列。
2.python插入排序代码
代码如下:
def insertion_sort(list2): for i in range(1, len(list2)): save = list2[i] j = i while j > 0 and list2[j – 1] > save: list2[j] = list2[j – 1] j -= 1 list2[j] = save
结果：[2, 3, 4, 21, 33, 44, 45, 67]
3.时间复杂度：o(n*n)