1、简介

  • 列表被分为有序区和无序区两个部分。最初有序区只有一个元素。
  • 每次从无序区选择一个元素，插入到有序区的位置，知道无序区变空。

image.png

2、插入排序的思路图

首先，我们有一个无序序列，最初的有序区只有一个(注：红色代表有序区，白色代表无序区)
image.png
第一趟插入：将第2个元素插入有序序列，但是发现 第2个元素本来就有序的，所以不用动，生成有序序列 [5,7]
image.png

第二趟插入：将第3个元素值为 4 插入前面的有序序列中，前面两个是有序的，[5,7]需要同时想右移动，得出有序序列为：[4,5,7]
image.png

第三趟插入：将第4个元素值为6 插入到 前面的有序序列中，这样，发现 7 需要向右移动，那么值为6的元素插入到7所在的位置，这样得出，有序序列为：[4,5,6,7]
image.png

第四趟插入：将第5个元素值为3 插入到 前面的有序序列中，这样，发现[4,5,6,7]都需要同时需要向右移动，那么值为3的元素插入到4所在的位置，这样得出，有序序列为：[3,4,5,6,7]
image.png

第五趟插入：将第6个元素值为1 插入到 前面的有序序列中，这样，发现[3,4,5,6,7]都需要同时需要向右移动，那么值为3的元素插入到4所在的位置，这样得出，有序序列为：[1,3,4,5,6,7]
image.png

第六趟插入：将第6个元素值为2 插入到 前面的有序序列中，这样，发现[3,4,5,6,7]都需要同时需要向右移动，那么值为2的元素插入到值为3所在的位置，这样得出，有序序列为：[1,2,3,4,5,6,7]
image.png
依次类推：
第n-1趟比较：讲第n个元素插入前面的有序子序列中，前面n-1个元素是有序的，而且是成片的向右移动。

3、插入排序实现

3.1、插入排序

根据上面的思路，我们来实现插入排序，代码如下：

  1. def insert_sort(li):
  2.     """插入排序"""
  4.     for i in range(1,len(li)):
  5.         tmp = li[i]  #抽到的牌
  7.         j = i - 1   #找到前面那个值的位置，跟它比大小
  9.         #j>=0:j必须是>=0, =0的话就是到第1个位置了，小于0就是负数了，所以不能小于0
  10.         #li[j] > tmp：表示当我抽到的牌(tmp) 大于前面那个数的时候就停止
  11.         while j >= 0 and li[j] > tmp:
  13.             li[j+1] = li[j]   #满足上述条件，我就往右边移动一个
  14.             j = j - 1         #再找到再左边的一个值的下标
  16.         li[j+1] = tmp #比你大的值都移完之后，这个时候插入我们的牌(tmp)

时间复杂度：O(n²)
优化空间：应用二分法查找来寻找插入点(并没有什么软用)