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

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