用python實現插入排序演算法

我們知道在計算機求解問題的過程中常常得用到排序,雖然我們所使用的面向對象語言已為我們提供了排序方法的實現. 但當我們打開實現層面的那個"蓋子"之後,不驚嘆然語言設計及演算法實現之精妙.

在市面上的書籍中常常有<<數據結構與演算法(_blank版)>>,_blank可以用C,Java等老牌的主流計算機語言來替代.其實現方式的優劣由於語言本身的特性各有千秋.

python作為簡單,強大,面向對象的動態語言,其語法的優雅性讓人讚嘆不已.雖然其屏蔽了C語言中重要的指針這一數據類型,影響到鏈表這種數據結構的實現. 但其在語法上的優雅性值得我們去實現一些常用的數據結構和演算法.(例如變數a,b交換,python 中只需要 a,b = b, a 即可,而這在其他語言中不合語法的.)

下面我們談談插入排序演算法:排序演算法有好幾十種,但大多數排序演算法逃離不了以下五種:插入排序,交換排序,選擇排序,歸併排序,基數排序. 因為其他排序是以上五種排序演算法的變種或變形, 例如冒泡排序是交換排序的一種. 掌握以上幾種排序的核心思想,實現方式是對排序演算法進一步理解至關重要要的一部.

以下開始談談我用最明了的方式說說插入排序: 插入排序,顧名思義在於"插入",那怎麼插入呢?我們可以用撲克牌抓牌來模擬:

1.首先有一堆無序的牌背面朝上在桌子上,我們先抓一張在手上

2.再抓一張與手上那張比較(我是左撇子),如果大了就放在手上那張牌的右邊,小了就插入到手上那張牌的左邊.這樣手上來兩張牌是有序了

3.再抓第三張牌,從右往左將它與手中的每張牌進行比較,直到有牌比它小,插入到這張比它小的牌的右邊.這樣手上的牌依舊有序的

4.反覆執行以上步驟,直到最後一張牌排好序...這樣手中的所有牌都有序的了.

下面我們具體分析下怎麼用python語言去實現:

比如共有n張牌,我們用python中的列表來存儲

例如:myList = [2,1,5,3,7,4,2]

len(myList) = 7

當抓第i張牌(從零開始)的時候:可分割為 [0,i-1], [i] ,[i+1,len(myList)]

手中的有序牌[0,i-1]

要插入的牌 [i]

桌子上為排序的牌 [i+1,len(myList)]

這樣我們用python語言來實現下

myList = [2,1,5,3,4,2,7] #從i=1(第二張牌開始)for i in range(1,len(myList)): #要排序的牌 key = myList[i] #手中右邊的牌 j = i - 1 #與 手中的牌逐一比較 while j >= 0 and myList[j] > key: #滿足條件時,交換兩張牌的順序 myList[j+1] = myList[j] j -= 1 #當不滿足時,即該牌比手中所有牌都大,放在最右邊 myList[j+1] = keyprint(myList)

推薦閱讀：