首頁  >  文章  >  後端開發  >  詳解Python中使用插入排序演算法的簡單分析與程式碼範例

詳解Python中使用插入排序演算法的簡單分析與程式碼範例

高洛峰
高洛峰原創
2017-03-06 13:32:561283瀏覽

問題描述

將一組隨機排列的數字重新依照從小到大的順序排列。

插入演算法

每次從陣列中取一個數字,與現有數字比較並插入適當位置。

如此重複,每次都能保持現有數字依照順序排列,直到數字取完,也就是排序成功。

這很像打牌時的抓牌狀況,

第一個條件:保持手上的牌的順序是正確的
第二個條件:每次抓到新的牌均依照順序插入手上的牌中間。
保證這兩條不變,那麼無論抓了幾張牌,最後手上的牌都是依照順序排列的。

Python 實作:

def insertion_sort(n):
 if len(n) == 1:
  return n
 b = insertion_sort(n[1:])
 m = len(b)
 for i in range(m):
  if n[0] <= b[i]:
   return b[:i]+[n[0]]+b[i:]
 return b + [n[0]]

   
另一個版本:

#
def insertion_sort(lst):
 if len(lst) == 1:
  return lst

 for i in xrange(1, len(lst)):
  temp = lst[i]
  j = i - 1
  while j >= 0 and temp < lst[j]:
   lst[j + 1] = lst[j]
   j -= 1
  lst[j + 1] = temp
 return lst


更多詳解Python中使用插入排序演算法的簡單分析與程式碼範例相關文章請關注PHP中文網!

陳述:
本文內容由網友自願投稿,版權歸原作者所有。本站不承擔相應的法律責任。如發現涉嫌抄襲或侵權的內容,請聯絡admin@php.cn