关键点
- 无序区
- 有序区，一开始第一个元素就在有序区，每次从无序区选择一个元素，插入到有序区中，直到无序区变为空
-
插入的两种情况
i表示要插入的无序区元素下标，j表示当前需要跟i进行比较的有序区下标，j初始值=i-1，比较后如果不满足比i指向的值小就继续-1
情况1：有序区找到比i指向小的元素，此时应该插入到 j+1 的位置
第一种情况
情况2：有序区没有找到比i指向小的元素，此时也应该插入到 j+1 的位置
第二种情况
代码实现
#时间复杂度O(n^2)
def insert_sort(li):
n = len(li)#li下标从0开始
for i in range(1,n):#共n-1趟，每趟中的i即无序区第一个元素下标
tmp = li[i] #要插入的元素，即i指向的元素
j = i - 1
while j >=0 and li[j] > tmp:#满足这两个条件，j会继续向前移动。反过来如果j等于-1或者li[j]<tmp就停止移动
li[j+1] = li[j]
j -= 1
#比较结束的两种情况(j等于-1或者li[j]<tmp)，都是插入到j+1位置
li[j + 1] = tmp
布尔短路问题
print(3 and 5) #打印 5
print(0 and 5) #打印 0
- a and b ，如果a是 False，整个结果必定为 False，b无需计算；如果a是 True，整个结果取决于 b，因此还要计算b
- a or b，如果a是True，整个计算结果必定为 True，b无需计算；如果a是 False，整个结果取决于 b，因此还要计算b
上面的条件while j >=0 and li[j] > tmp:，当j等于-1，不会计算li[j] > tmp，直接返回False
如果修改成while li[j] > tmp and j >=0:，当j等于-1，先计算li[j] > tmp，在python中li[-1]是支持的，其他语言不支持该语法就会有异常
