上次我们讨论了选择排序，这次我们来介绍一下插入排序。其核心原理是随机给定一个列表中的n个数字, 将该列表分为两部分。第一部分为已排序列表, 第二部分为未排序列表。最开始的时候已排序列表只有原列表的第1个元素, 原列表剩余的n-1个元素纳入未排序列表。排序执行n-1轮步骤如下：

第1轮: 从未排序列表的最末端获取一个元素a, 将该元素a与已排序列表的最后一个元素b进行比较。 如a>=b则将a插入b的后面, 结束排序; 如a<b, 则将a插入b的前面, 结束本轮排序。

第2轮: 从未排序列表的最末端获取一个元素a, 将该元素a与已排序列表的最后一个元素b进行比较。 如b<a则将a插入b的后面, 结束排序; 如b>a, 则继续将a与b之前的c进行比较; 如c<a则将a插入b之前c之后, 结束排序; 如c>a, 则将a插入c的前面, 结束本轮排序。

......

第n-1轮: 从未排序列表的最左侧获取一个元素, 将该元素与已排序列表从右向左所有的元素逐一比较，直到找到自己的位置并插入后, 结束本轮排序。

排序结束。

以下为实现的代码：

# coding: utf-8# import randomdef my_insert(my_list=[]):    my_list1 = my_list[0:1]  # 已排序列表    my_list2 = my_list[1:]    # 未排序列表    while my_list2:        value = my_list2.pop()        index = len(my_list1) - 1        for i in list(range(len(my_list1)))[::-1]:            if value < my_list1[i]:                index = i            else:                if value > my_list1[-1]:                    my_list1.append(value)                else:                    my_list1.insert(index, value)                break        else:            my_list1.insert(index, value)    return my_list1if __name__ == "__main__":    # elements_list = [random.randint(1, 100) for i in range(10)]    elements_list = [71, 47, 4, 32, 77, 99, 56, 14, 7, 54]    print("排序之前: ", elements_list)    elements_list = my_insert(elements_list)    print("排序之后: ", elements_list)

不足之处请批评指正，欢迎讨论~~~