Python實(shí)現(xiàn)插入排序和選擇排序的方法
話不多說，讓我們從最基本的排序算法開始吧
插入排序
如下圖所示，插入排序的實(shí)現(xiàn)思路顧名思義，就是 不斷地在一個(gè)已經(jīng)是有序的數(shù)組中，尋找合適位置并插入新元素 。
具體實(shí)現(xiàn)步驟為：
首先我們把整個(gè)數(shù)組拆分為有序區(qū)間和未排序區(qū)間，有序區(qū)間在插入排序一開始只有一個(gè)元素，就是數(shù)組的第一個(gè)元素。
接在有序區(qū)間之后的一個(gè)元素就是準(zhǔn)備插入的元素，在圖中就是標(biāo)為綠色的元素，在有序區(qū)間內(nèi)尋找位置并插入。
其尋找邏輯為：從后往前依次進(jìn)行比較，如果待插入元素大于當(dāng)前元素，則將待插入元素插入到當(dāng)前元素的后一位，如果待插入元素小于當(dāng)前元素，則將當(dāng)前元素后移一位。不斷重復(fù)該過程直至到數(shù)組的最后一位
其實(shí)現(xiàn)的具體代碼為：
def insertion_sort(a):
length = len(a)
if length <=1:
return
for i in range(1,length):
j = i-1
value = a[i]
while j >=0:
if a[j]<value:
a[j+1] = value
break
else:
a[j+1] = a[j]
if j == 0:
a[j] = value
j -=1
print(a)
return a時(shí)間復(fù)雜計(jì)算為：我們需要將整個(gè)數(shù)組遍歷一遍，所以這一部分為O(n)，在每一次遍歷中都要執(zhí)行一次插入操作，其時(shí)間復(fù)雜度為O(n)，所以總時(shí)間復(fù)雜度為O(n2)
選擇排序
選擇排序跟插入排序算法類似，都是將數(shù)組分為有序區(qū)間和未排序區(qū)間，區(qū)別在于插入排序是將一個(gè)新元素插入到有序區(qū)間內(nèi)，而選擇排序則是在未排序區(qū)間中找到最小元素，并交換到有序區(qū)間之后。
實(shí)現(xiàn)代碼為：
def selection_sort(a):
length = len(a)
if length <=1:
return
for i in range(0,length-1):
min_value = a[i]
min_index = i
j = i+1
while j<length:
if a[j] < min_value:
min_value = a[j]
min_index = j
j += 1
a[i],a[min_index] = a[min_index],a[i]
return a時(shí)間復(fù)雜度計(jì)算：數(shù)組長(zhǎng)度為n，一共需要尋找n次最小值，每次尋找最小值都要遍歷未排序區(qū)間一次，其時(shí)間復(fù)雜度為O(n)，乘以n次為O(n2)
- Python實(shí)現(xiàn)的插入排序，冒泡排序，快速排序，選擇排序算法示例
- Python排序算法之選擇排序定義與用法示例
- Python 實(shí)現(xiàn)選擇排序的算法步驟
- Python排序搜索基本算法之選擇排序?qū)嵗治?/a>
- Python tkinter 樹形列表控件(Treeview)的使用方法
- python GUI庫圖形界面開發(fā)之PyQt5樹形結(jié)構(gòu)控件QTreeWidget詳細(xì)使用方法與實(shí)例
- 一行python實(shí)現(xiàn)樹形結(jié)構(gòu)的方法
- python實(shí)現(xiàn)樹形打印目錄結(jié)構(gòu)
- Python如何生成樹形圖案
- Python 選擇排序中的樹形選擇排序
相關(guān)文章
Python3交互式shell ipython3安裝及使用詳解
這篇文章主要介紹了Python3交互式shell ipython3安裝及使用詳解,文中通過示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友可以參考下2020-07-07
Pygame實(shí)戰(zhàn)之檢測(cè)按鍵正確的小游戲
這篇文章主要為大家介紹了利用Pygame模塊實(shí)現(xiàn)的檢測(cè)按鍵正確的小游戲：每個(gè)字母有10秒的按鍵時(shí)間，如果按對(duì)，則隨機(jī)產(chǎn)生新的字符，一共60s,如果時(shí)間到了，則游戲結(jié)束?？靵砀S小編一起學(xué)習(xí)一下吧2021-12-12
Python中實(shí)現(xiàn)字符串類型與字典類型相互轉(zhuǎn)換的方法
這篇文章主要介紹了Python中實(shí)現(xiàn)字符串類型與字典類型相互轉(zhuǎn)換的方法,非常實(shí)用,需要的朋友可以參考下2014-08-08
python自然語言處理之字典樹知識(shí)總結(jié)
這篇文章主要介紹了python自然語言處理之字典樹知識(shí)總結(jié),文中有非常詳細(xì)的代碼示例,對(duì)正在學(xué)習(xí)python的小伙伴們有非常好的幫助,需要的朋友可以參考下2021-04-04
2009-05-05
Numpy數(shù)組array和矩陣matrix轉(zhuǎn)換方法
這篇文章主要介紹了Numpy數(shù)組array和矩陣matrix轉(zhuǎn)換方法，文中通過示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2019-08-08
Python人工智能之路 jieba gensim 最好別分家之最簡(jiǎn)單的相似度實(shí)現(xiàn)
這篇文章主要介紹了Python人工智能之路 jieba gensim 最好別分家之最簡(jiǎn)單的相似度實(shí)現(xiàn) ,非常不錯(cuò)，具有一定的參考借鑒價(jià)值，需要的朋友可以參考下2019-08-08
python對(duì)視頻畫框標(biāo)記后保存的方法
今天小編就為大家分享一篇python對(duì)視頻畫框標(biāo)記后保存的方法，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。一起跟隨小編過來看看吧2018-12-12
這篇文章主要介紹了淺談python中的占位符，分享了其簡(jiǎn)單實(shí)例，具有一定參考價(jià)值，需要的朋友可以了解下。2017-11-11
Python中input()函數(shù)的用法實(shí)例小結(jié)
我們編寫的大部分程序,都需要讀取輸入并對(duì)其進(jìn)行處理,而基本的輸入操作是從鍵盤鍵入數(shù)據(jù),Python從鍵盤鍵入數(shù)據(jù),大多使用其內(nèi)置的input（）函數(shù),下面這篇文章主要給大家介紹了關(guān)于Python中input()函數(shù)用法的相關(guān)資料,需要的朋友可以參考下2022-03-03