關鍵點
- 無序區(qū)
- 有序區(qū)，一開始第一個元素就在有序區(qū)崔步，每次從無序區(qū)選擇一個元素稳吮，插入到有序區(qū)中，直到無序區(qū)變?yōu)榭?/li>
-
插入的兩種情況
i表示要插入的無序區(qū)元素下標井濒，j表示當前需要跟i進行比較的有序區(qū)下標灶似，j初始值=i-1，比較后如果不滿足比i指向的值小就繼續(xù)-1
情況1：有序區(qū)找到比i指向小的元素瑞你，此時應該插入到 j+1 的位置
第一種情況
情況2：有序區(qū)沒有找到比i指向小的元素酪惭，此時也應該插入到 j+1 的位置
第二種情況
代碼實現(xiàn)
#時間復雜度O(n^2)
def insert_sort(li):
n = len(li)#li下標從0開始
for i in range(1,n):#共n-1趟，每趟中的i即無序區(qū)第一個元素下標
tmp = li[i] #要插入的元素者甲，即i指向的元素
j = i - 1
while j >=0 and li[j] > tmp:#滿足這兩個條件春感，j會繼續(xù)向前移動。反過來如果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]是支持的姑蓝，其他語言不支持該語法就會有異常
