欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

Python中使用插入排序算法的簡單分析與代碼示例

 更新時(shí)間：2016年05月04日 09:57:57   投稿：goldensun  
這篇文章主要介紹了Python使用插入排序算法的簡單分析與代碼示例,插入算法的平均時(shí)間復(fù)雜度為O(n^2),需要的朋友可以參考下

問題描述

將一組隨機(jī)排列的數(shù)字重新按照從小到大的順序排列。

插入算法

每次從數(shù)組中取一個(gè)數(shù)字，與現(xiàn)有數(shù)字比較并插入適當(dāng)位置。

如此重復(fù)，每次均可以保持現(xiàn)有數(shù)字按照順序排列，直到數(shù)字取完，即排序成功。

這很像打牌時(shí)的抓牌情況，

第一個(gè)條件：保持手上的牌的順序是正確的
第二個(gè)條件：每次抓到新的牌均按照順序插入手上的牌中間。
保證這兩條不變，那么無論抓了幾張牌，最后手上的牌都是依照順序排列的。

Python 實(shí)現(xiàn)：

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]]

   
另一個(gè)版本：

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

相關(guān)文章

最新評論