插入排序就是每一步都將一個(gè)待排數(shù)據(jù)按其大小插入到已經(jīng)排序的數(shù)據(jù)中的適當(dāng)位置，直到全部插入完畢岳锁。
- 默認(rèn)序列中的第0個(gè)元素是有序的（因?yàn)橹挥幸粋€(gè)元素a[0]嘛圆米，自然是有序的）；
- 從下標(biāo)為1（下標(biāo)0沒(méi)啥好插的）的元素開(kāi)始声畏，取當(dāng)前下標(biāo)i位置處的元素a[i]保存到一個(gè)臨時(shí)變量waitInsert里撞叽；
- waitInsert與對(duì)前半部分有序序列的循環(huán)遍歷比較，直到遇到第一個(gè)比waitInsert大的元素（這里默認(rèn)是從小到大排序）插龄，此時(shí)的下標(biāo)為j愿棋，然后將其插入到j(luò)的位置即可；
- 因?yàn)榍懊娴牟迦刖危瑢?dǎo)致后面元素向后推移一個(gè)位置糠雨，沒(méi)關(guān)系，把原來(lái)下標(biāo)i的元素彈出即可徘跪；
- 重復(fù)進(jìn)行第2步到第4步甘邀，直到亂序序列中的元素被全部插入到有序序列中；
- 經(jīng)過(guò)以上5個(gè)步驟之后垮庐，整體序列必然有序松邪，排序完成。
# 直接插入排序
def insertSort(relist):
len_ = len(relist)
for i in range(1,len_):
for j in range(i):
if relist[i] < relist[j]:
relist.insert(j,relist[i]) # 首先碰到第一個(gè)比自己大的數(shù)字突硝，趕緊剎車(chē)测摔，停在那，所以選擇insert
relist.pop(i+1) # 因?yàn)榍懊娴膇nsert操作，所以后面位數(shù)+1锋八，這個(gè)位置的數(shù)已經(jīng)insert到前面去了浙于，所以pop彈出
break
return relist
print insertSort([1,5,2,6,9,3])
