友好簡單的排序算法——插入排序钓丰。直接看程序或者看定義之類直接講解的文字，我覺得還是不太好理解。
其實插入排序更適合一部分已經(jīng)有序的序列靴姿，比如1,2,3,4,5,6,9,8,7。
我們應(yīng)該都摸過撲克牌吧磁滚，或者搓過麻將吧佛吓。我說的是實體的牌，不是換了斗地主還有麻將垂攘。
我們來回憶一下维雇，當我們拿到一張新牌，我們在干什么晒他？當我們拿到一堆沒有序的牌我們在干什么吱型？
我們在給牌排序，無論是從A陨仅，2唁影，3耕陷，……，K据沈，還是從2哟沫，A，K锌介，Q嗜诀，……3。我們總是從一張牌開始孔祸，然后拿到一張新的隆敢，放到它應(yīng)該在的位置，直到我們?nèi)颗藕梦覀兊呐啤?/p>
打麻將時崔慧，摸到一張新的牌拂蝎，但是又不需要打出去時，我們也會把它放到它應(yīng)該在的位置惶室，我們在開始打麻將時就會把牌排好温自，直接插就行。
如果你沒打過麻將皇钞，沒有打過撲克悼泌，……，我也不知道怎么辦了夹界。
插入排序的原理和我們打撲克搓麻將是一樣的馆里。上面的兩個例子，剛好就說明了我們的過程可柿。兩種鸠踪，一是給一堆沒有順序的序列排序，二是給一個新的元素插入到一個有序的序列中复斥。
我們把第一個元素看作一個有序的序列营密，后面的看作無序的待插入的序列。從第二個數(shù)開始永票，將其與其前一個數(shù)比較，如果不符合我們要求的排序順序（升序或者降序滥沫，或者我們自己定義的規(guī)則）侣集，則互換位置，然后再與前一個數(shù)作比較直到滿足我們的排序順序兰绣。然后再將下一個數(shù)進行排序世分，直到全部完成。
例如 5, 3, 2, 6 的排序過程：
- 5, 3, 2, 6
- 3, 5, 2, 6
- 3, 5, 2, 6
- 3, 2, 5, 6
- 2, 3, 5, 6
- 2, 3, 5, 6
- 2, 3, 5, 6
這樣就很好理解缀辩，但是還不夠好臭埋。后面再來優(yōu)化踪央，我們先來實現(xiàn)這個insertion_sort():
def insertion_sort(a):
for i in range(1,len(a)): # 插入排序從第二個位置開始
for j in range(i, 0, -1):
if a[j] < a[j-1]:
a[j], a[j-1] = a[j-1], a[j]
a = [9, 7, 5, 6, 3, 2, 1, 4, 8]
insertion_sort(a)
print(a)
輸出結(jié)果為：
這樣一個簡單的插入排序算法就實現(xiàn)出來了。
前面說的可以優(yōu)化是這樣瓢阴，每一次排序時畅蹂，我們都需要將當前值與其前面的數(shù)互換位置m次，m是比較后不滿足要求的次數(shù)荣恐。所以如果第k個數(shù)需要排在第一位液斜，那么他就需要互換位置k-1次〉拢互換位置在python中直接用一個語句就可以完成少漆，但是在其他的語言中就需要用一個臨時值來做過渡，才能夠完成硼被，所以我們應(yīng)該減少互換位置的次數(shù)示损。
我在前面的撲克牌的舉例中，已經(jīng)加粗了相關(guān)的部分嚷硫，就是應(yīng)該在的位置检访。我們先存儲當前排序的數(shù)，然后找到它應(yīng)該在的位置论巍，然后將這個位置空出來烛谊，并把記錄的值放到這個位置。也就是把這個位置之后的元素嘉汰，都后移一個位置丹禀，然后插入，這真的是非常形象了鞋怀。
下面我們來實現(xiàn)這個排序算法：
def new_insertion_sort(a):
for i in range(1, len(a)): # 插入排序從第二個位置開始
cur = a[i] # 保存當前的值
j = i # 用于尋找cur應(yīng)該在的位置
while j > 0:
if a[j-1] > cur:
a[j] = a[j-1]
j -= 1
else:
break
a[j] = cur
當然我們還可以改進：
def new_insertion_sort(a):
for i in range(1, len(a)): # 插入排序從第二個位置開始
cur = a[i] # 保存當前的值
j = i # 用于尋找cur應(yīng)該在的位置
while j > 0 and a[j-1] > cur:
a[j] = a[j-1]
j -= 1
a[j] = cur
最后的結(jié)果是一樣的：
