問題描述
將一組隨機排列的數字重新依照從小到大的順序排列。
插入演算法
每次從陣列中取一個數字,與現有數字比較並插入適當位置。
如此重複,每次都能保持現有數字依照順序排列,直到數字取完,也就是排序成功。
這很像打牌時的抓牌狀況,
第一個條件:保持手上的牌的順序是正確的
第二個條件:每次抓到新的牌均依照順序插入手上的牌中間。
保證這兩條不變,那麼無論抓了幾張牌,最後手上的牌都是依照順序排列的。
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中文網!