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

更新時間：2016年05月04日 09:57:57 投稿：goldensun

這篇文章主要介紹了Python使用插入排序算法的簡單分析與代碼示例,插入算法的平均時間復雜度為O(n^2),需要的朋友可以參考下

問題描述

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

插入算法

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

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

這很像打牌時的抓牌情況，

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

Python 實現(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]]

另一個版本：

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)文章

Python中如何導入類示例詳解
這篇文章主要給大家介紹了關(guān)于Python中如何導入類的相關(guān)資料，文中通過示例代碼介紹的非常詳細，對大家學習或者使用Python具有一定的參考學習價值，需要的朋友們下面來一起學習學習吧
2019-04-04
python concurrent.futures模塊的使用測試
大家都知道concurrent.futures 是 3.2 中引入的新模塊，它為異步執(zhí)行可調(diào)用對象提供了高層接口，今天通過本文給大家介紹python concurrent.futures模塊的使用測試，感興趣的朋友一起看看吧
2021-07-07
解讀matplotlib和seaborn顏色圖(colormap)和調(diào)色板(color palette)
這篇文章主要介紹了matplotlib和seaborn顏色圖(colormap)和調(diào)色板(color palette)，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教
2023-06-06
Github?Copilot結(jié)合python的使用方法詳解
最近也是聽說github出了一種最新的插件叫做copilot,于是申請了,下面這篇文章主要給大家介紹了關(guān)于Github?Copilot結(jié)合python使用的相關(guān)資料,需要的朋友可以參考下
2022-04-04
Python如何將大TXT文件分割成4KB小文件
處理大文本文件是程序員經(jīng)常遇到的挑戰(zhàn),特別是當我們需要把一個幾百MB甚至幾個GB的TXT文件分割成小塊時,下面我們來聊聊如何用Python自動完成這個任務吧
2025-04-04
使用Python OpenCV為CNN增加圖像樣本的實現(xiàn)
這篇文章主要介紹了使用Python OpenCV為CNN增加圖像樣本的實現(xiàn)，小編覺得挺不錯的，現(xiàn)在分享給大家，也給大家做個參考。一起跟隨小編過來看看吧
2019-06-06
Python數(shù)據(jù)庫sqlite3圖文實例詳解
SQLite是一個進程內(nèi)的庫,實現(xiàn)了自給自足的、無服務器的、零配置的、事務性的SQL數(shù)據(jù)庫引擎,下面這篇文章主要給大家介紹了關(guān)于Python數(shù)據(jù)庫sqlite3的相關(guān)資料,需要的朋友可以參考下
2022-09-09
Python中新式類與經(jīng)典類的區(qū)別詳析
這篇文章主要給大家介紹了關(guān)于Python中新式類與經(jīng)典類的區(qū)別，文中通過示例代碼介紹的非常詳細，對大家學習或者使用Python具有一定的參考學習價值，需要的朋友們下面來一起學習學習吧
2019-07-07
Python shutil模塊文件和目錄操作示例詳解
本文將會學習到?shutil?模塊,包括其主要功能和示例代碼,以幫助你更好地理解如何使用它來處理文件和目錄
2023-11-11
python讀csv文件時指定行為表頭或無表頭的方法
這篇文章主要介紹了python讀csv文件時指定行為表頭或無表頭的方法，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧
2019-06-06