Python排序算法之直接插入排序

插入排序的主要思想是每次取一個列表元素與列表中已經排序好的列表段進行比較，然後插入從而得到新的排序好的列表段，最終獲得排序好的列表。

比如，待排序列表為[49,38,65,97,76,13,27,49]，則比較的步驟和得到的新列表如下：

(帶有背景顏色的列表段是已經排序好的，紅色背景標記的是執行插入並且進行過交換的元素）

時間復雜度：O(n^2)

待排序： 　　　　[49,38,65,97,76,13,27,49]

第一次比較後：　 [38,49,65,97,76,13,27,49]     第二個元素（38）與之前的元素進行比較，發現38較小，進行交換

第二次比較後：　 [38,49,65,97,76,13,27,49]　  第三個元素（65）大於前一個元素（49），所以不進行交換操作，直接到下一個元素比較

第三次比較後： 　[38,49,65,97,76,13,27,49]　  和第二次比較類似

第四次比較後：　 [38,49,65,76,97,13,27,49]　  當前元素（76）比前一元素（97）小，（97）後移，（76）繼續與（65）比較，發現當前元素比較大，執行插入

第五次比較後：　 [13,38,49,65,76,97,27,49]　　

第六次比較後：　 [13,27,38,49,65,76,97,49]

第七次比較後：　 [13,27,38,49,49,65,76,97] 

從百度百科上盜了一張圖：

Python實現代碼如下：

 # Coded by Alvin
 
 
 def InsertSort(myList):
     #獲取列表長度
     length = len(myList)
 
     for i in range(1,length):
         #設置當前值前一個元素的標識
         j = i - 1
         
         #如果當前值小於前一個元素,則將當前值作為一個臨時變量存儲,將前一個元素後移一位
         if(myList[i] < myList[j]):
             temp = myList[i]
             myList[i] = myList[j]
             
             #繼續往前尋找,如果有比臨時變量大的數字,則後移一位,直到找到比臨時變量小的元素或者達到列表第一個元素
             j = j-1
             while j>=0 and myList[j] > temp:
                 myList[j+1] = myList[j]
                 j = j-1
 
             #將臨時變量賦值給合適位置
             myList[j+1] = temp
 
 
 myList = [49,38,65,97,76,13,27,49]
 InsertSort(myList)
 print(myList)

運行結果：