插入排序的主要思想就是：
每次取得一個列表元素阁最，與已排序好的列表進行比較拱层，然后插入相應的位置，最終獲得排序好的列表绿渣。
意思是這樣的：
一個未排序的列表：
下標： 0 1 2 3 4
數組：[5,4,3,2,1]
我們把列表分成兩個部分seqOK,seqNo（只是在一個列表中劃分成兩個部分朝群，而不是截取成兩個列表），已排序好(seqOK)和未排序好(seqNo)的列表中符。
我們認為列表的第一個元素是已經排序好的姜胖，只要一個元素嘛，還想怎么排淀散？余下的部分是未排序好的列表谭期。
使用未排序的列表(seqNo)中的第一個元素 a ，對比已經排序好的列表(seqNo)中的每一個元素吧凉，從后往前對比隧出。如果 seqOk[i] > a，則對比排序好的列表seqOK中的下一個 seqOk[i-1]阀捅。直到seqOk[i] < a的時候 將a插入當前位置胀瞪。
依次seqNo中的每一個元素，最終獲得排序好的列表。
算法導論中的 排序算法 實現如下：
代碼如下：
seq = [5, 4, 0, 3, 2, 1]
print '排序前: ',seq
for i in range(1,len(seq)):
temp = seq[i]
index = i-1
while index >= 0 and seq[index] > temp:
seq[index+1] = seq[index]
index -= 1
seq[index+1] = temp
print '第 %s 次排序后' %i ,seq
print '排序后：',seq```
運行結果如下：
還有一種實現方式如下：
seq = [5, 4, 0, 3, 2, 1]
print '排序前: ', seq
for i in range(1,len(seq)):
temp = seq.pop(i)
index = i-1
while index > 0 and seq[index]>temp:
index -= 1
#這個地方需要判斷一次
if index == 0 and temp > seq[index]:
index += 1
seq.insert(index,temp)
print '第 %s 次排序后' % i, seq
print '排序后：', seq
運行結果如下：
代碼中為什么需要判斷一次呢凄诞？
例如：[5, 4, 0, 3, 2, 1]
第一次循環(huán)的時候 i == 1 也就 temp == 4圆雁，index == 0，因為index == 0 所有while根本就沒有執(zhí)行帆谍，也就是說 seq[index]>temp根本就沒有比較就直接把元素插入index前面伪朽，也就是 把4 插入到 5的前面。
當列表排序為 [0,4,5,3,2,1]的時候：
此時 i == 3 也就是 temp == 3, index==2汛蝙。依次比較：seq[index]>temp
第一次：index == 2 烈涮，5>3 則 index -= 1。
第二次：index == 1窖剑， 4>3 則 index -= 1坚洽。
第三次：index == 0，但是 while index>0 不成立西土，所以 seq[index]>temp也就是0>3并沒有進行比較讶舰。
循環(huán)結束：此時index == 0 ，seq.insert(index,temp）將3插入下標index 0之前需了。
所以排序后的結果為： [3,0,4,5,2,1]
所以在插入之前要判斷一下是不是到達第一個元素了 也就是下標index == 0的時候 如果：temp > seq[index]跳昼，則插入index的后面，而不是前面肋乍。
也就是說 當index==0的時候鹅颊，此時 temp == 3，seq[index] == 0,這時候3要插入到0的后面住拭，插入前面就錯了挪略。
代碼如下：
seq = [5, 4,0,3, 2, 1]
print '排序前: ', seq
for i in range(1,len(seq)):
temp = seq.pop(i)
index = i-1
while index > 0 and seq[index]>temp:
index -= 1
seq.insert(index,temp)
print '第 %s 次排序后' % i, seq
print '排序后：', seq
運行結果如下：
我們對比一下 兩種排序方式：
第一種：每次對比都把符合條件的元素后移一位历帚。
while index >= 0 and seq[index] > temp:
seq[index+1] = seq[index]
index -= 1
第二種：每次循環(huán)只需要彈出元素一次滔岳，插入元素一次。彈出挽牢，插入時數據結構的變化是python幫我們維護的谱煤，可能比我們手動來維護性能高一些吧。
temp = seq.pop(i)
index = i-1
while index > 0 and seq[index]>temp:
index -= 1
if index == 0 and temp > seq[index]:
index += 1
seq.insert(index,temp)
我們來對比一下運行時間：
def haoshi(func):
def wapper():
start_time = time.time()
func()
print func.name,'耗時 ',time.time()-start_time
return wapper
@haoshi
def charu1():
"""第一種種排序插入方式"""
seq = range(10000)[::-1]
for i in range(1,len(seq)):
temp = seq[i]
index = i-1
while index >= 0 and seq[index] > temp:
seq[index+1] = seq[index]
index -= 1
seq[index+1] = temp
@haoshi
def charu2():
"""第二種排序插入方式"""
seq = range(10000)[::-1]
for i in range(1,len(seq)):
temp = seq.pop(i)
index = i-1
while index > 0 and seq[index]>temp:
index -= 1
if index == 0 and temp > seq[index]:
index += 1
seq.insert(index,temp)
charu1()
charu2()
運行結果如下：
