Python排序算法之插入排序及其優(yōu)化方案詳解
一、插入排序
插入排序與我們平時(shí)打撲克牌非常相似,將新摸到的牌插入到已有的牌中合適的位置,而已有的牌往往是有序的。
1.1 執(zhí)行流程
(1)在執(zhí)行過(guò)程中,插入排序會(huì)將序列分為2部分,頭部是已經(jīng)排好序的,尾部是待排序的。
(2)從頭開(kāi)始掃描每一個(gè)元素,每當(dāng)掃描到一個(gè)元素,就將它插入到頭部合適的位置,使得頭部數(shù)據(jù)依然保持有序
1.2 逆序?qū)?/h3>
數(shù)組 <2,3,8,6,1> 的逆序?qū)椋?lt;2,1> ❤️,1> <8,1> <8,6> <6,1>,共5個(gè)逆序?qū)Α?br />
插入排序的時(shí)間復(fù)雜度與逆序?qū)Φ臄?shù)量成正比關(guān)系,逆序?qū)Φ臄?shù)量越多,插入排序的消耗的時(shí)間就越多。
當(dāng)逆序?qū)Φ臄?shù)量極少時(shí),插入排序的效率特別高,甚至速度比 O nlogn 級(jí)別的快速排序還要快。
1.3 代碼實(shí)現(xiàn)
將一個(gè)元素插入到數(shù)組有序的前半部分中,那個(gè)插入的位置元素一定是比該元素大,而該位置前的元素比該元素?。ɑ蛘呤菦](méi)有前一個(gè)元素)。所以我們可以通過(guò)比較,將該元素進(jìn)行冒泡:如果前一個(gè)元素比我大,則交換位置,否則停止冒泡。
def insertion_sort_ver1(array): n=len(array) for right in range(1,n): cur=right while cur>0 and array[cur-1]>array[cur]: array[cur-1],array[cur]=array[cur],array[cur-1] cur-=1
整體代碼:
import numpy as np import time #檢查是否有序 def orderCheck(array): for i in range(len(array)-1): if array[i]>array[i+1]: print('排序失敗') return print('排序成功') def sort(sort_algorithm,ori_array): #先復(fù)制一份數(shù)組,再進(jìn)行更改 array = np.copy(ori_array) start=time.clock() sort_algorithm(array) end=time.clock() total_time=float(end-start) print(sort_algorithm.__name__+" : %0.5f" % total_time) orderCheck(array) def insertion_sort_ver1(array): n=len(array) for right in range(1,n): cur=right while cur>0 and array[cur-1]>array[cur]: array[cur-1],array[cur]=array[cur],array[cur-1] cur-=1 array=np.random.randint(0,10000,2000,dtype=int) sort(insertion_sort_ver1, array)
消耗時(shí)間為0.82632秒。
1.4 優(yōu)化1
在冒泡中,交換前后cur和cur-1位置兩個(gè)元素的位置,需要進(jìn)行兩次賦值,但如果冒泡仍要繼續(xù),cur-1位置的元素還是會(huì)被cur-2位置的元素覆蓋,所以?xún)纱钨x值中的一次其實(shí)是無(wú)意義的,為此我們可以先找到插入位置,然后將后方的元素作統(tǒng)一的移動(dòng);或者是在冒泡過(guò)程中只進(jìn)行一次賦值(將前一個(gè)元素移動(dòng)到后方),直到冒泡結(jié)束確定插入位置后,再進(jìn)行待插入元素的插入。
#元素交換作優(yōu)化 def insertion_sort_ver2(array): n=len(array) for right in range(1,n): cur=right elem=array[cur] while cur>0 and array[cur-1]>elem: array[cur]=array[cur-1] cur-=1 array[cur]=elem
消耗時(shí)間為0.45987秒,明顯變快了。
1.5 優(yōu)化2
之前我們?cè)趯ふ也迦氲奈恢脮r(shí),采用的是從大到小依次遍歷的方法,因?yàn)槭窃谝粋€(gè)有序的數(shù)組上尋找插入的位置,我們肯定會(huì)想到一種查找的方法:二分查找。通過(guò)二分查找,我們可以通過(guò)O(logn)級(jí)別的比較與O(n)級(jí)別的元素移動(dòng)完成排序任務(wù),而之前我們進(jìn)行的比較和移動(dòng),都是O(n)級(jí)別。
1.5.1 普通二分查找
普通的二分查找十分簡(jiǎn)單,根據(jù)中間位置元素大小更新兩端索引位置即可,在此兩端的索引 [left,right)采用左閉右開(kāi)的方式,這樣未查找到元素的條件就十分簡(jiǎn)單,因?yàn)閰^(qū)間左閉右開(kāi),當(dāng)left<right時(shí),表明區(qū)間內(nèi)還有元素,仍舊可以進(jìn)行查找;否則,區(qū)間里沒(méi)有元素了,說(shuō)明元素未查找到,代碼如下。
def binary_search(array,target):#[left,right)左閉右開(kāi) left=0 right=len(array) while left<right:#當(dāng)left<right,表明區(qū)間中還有值,否則哪怕left==right,因right不可取,區(qū)間中還是無(wú)值 middle = (left + right) >> 1 if target<array[middle]: right=middle elif array[middle]<target: left=middle+1 else: return middle return -1
1.5.2 二分查找插入位置
查找插入位置的二分查找顯然和普通二分不同,在此我們修改一下左右端點(diǎn)移動(dòng)的條件與移動(dòng)方式。在此左右端點(diǎn)依舊左閉右開(kāi),如果當(dāng)array[middle]小于或等于插入元素target,那么顯然middle不可能是插入位置,middle位置的元素也不再需要,left應(yīng)該為middle+1;而當(dāng)array[middle]大于target,那么middle有可能是插入的位置(插入位置大于target,前一個(gè)元素如果存在,應(yīng)小于target),應(yīng)該保留middle,所以right=middle。但是區(qū)間是左閉右開(kāi),right不可取到,哪怕right=middle,middle不還是無(wú)法取得嗎?但由于array[middle]不論取何值(不管是大于、等于、小于),都將導(dǎo)致左右端點(diǎn)left、right的變化,且數(shù)組中左右端點(diǎn)代表區(qū)間的大小是不斷減小的,最終左右端點(diǎn)重合,此時(shí)的位置就是插入的位置。
下面是查找的示例:
代碼如下:
def binary_search(array,index): left=0 right=index while left<right: middle=(left+right)>>1 if array[middle]>array[index]:#大于目標(biāo),可能是插入的位置,用right保留 right=middle else:#小于等于,不可能是插入位置,更新left為middle+1 left=middle+1 return left #最后插入的位置
1.5.3 使用二分的插入排序
找到插入位置后,我們只需移動(dòng)位置后面的元素,再將元素插入即可。
#利用二分查找找到插入的點(diǎn),減少了比較的次數(shù) def insertion_sort_ver3(array): n=len(array) for right in range(1,n): index=binary_search(array,right) elem=array[right] for i in range(right,index,-1): array[i]=array[i-1] array[index]=elem
可見(jiàn)速度比之前的插入排序仍有提高。
1.6 時(shí)間空間復(fù)雜度
最壞、平均時(shí)間復(fù)雜度:O(n^2),最好時(shí)間復(fù)雜度:O(n),空間復(fù)雜度:O(1)。
1.7 穩(wěn)定性
插入排序?qū)⒑蠓降脑貜暮笸安迦?,后邊相等的元素將插入在左邊相等元素的右?cè),沒(méi)有改變?cè)械奈恢?,屬于穩(wěn)定排序。
到此這篇關(guān)于Python排序算法之插入排序及其優(yōu)化方案詳解的文章就介紹到這了,更多相關(guān)Python插入排序內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!
- Python 數(shù)據(jù)結(jié)構(gòu)之十大經(jīng)典排序算法一文通關(guān)
- 如何利用Python動(dòng)態(tài)展示排序算法
- python數(shù)據(jù)結(jié)構(gòu)的排序算法
- python如何實(shí)現(xiàn)常用的五種排序算法詳解
- python3實(shí)現(xiàn)常見(jiàn)的排序算法(示例代碼)
- python排序算法的簡(jiǎn)單實(shí)現(xiàn)方法
- python實(shí)現(xiàn)經(jīng)典排序算法的示例代碼
- Python實(shí)現(xiàn)冒泡排序算法的完整實(shí)例
- Python?十大經(jīng)典排序算法實(shí)現(xiàn)詳解
相關(guān)文章
django的autoreload機(jī)制實(shí)現(xiàn)
這篇文章主要介紹了django的autoreload機(jī)制實(shí)現(xiàn),文中通過(guò)示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧2020-06-06Python虛擬機(jī)字節(jié)碼教程之控制流實(shí)現(xiàn)詳解
在本篇文章當(dāng)中主要給大家分析 python 當(dāng)中與控制流有關(guān)的字節(jié)碼,通過(guò)對(duì)這部分字節(jié)碼的了解,我們可以更加深入了解 python 字節(jié)碼的執(zhí)行過(guò)程和控制流實(shí)現(xiàn)原理2023-04-04利用Python進(jìn)行數(shù)據(jù)可視化常見(jiàn)的9種方法!超實(shí)用!
這篇文章主要給大家介紹了關(guān)于利用Python進(jìn)行數(shù)據(jù)可視化常見(jiàn)的9種方法!文中介紹的方法真的超實(shí)用!對(duì)大家學(xué)習(xí)或者使用python具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧2018-07-07關(guān)于Python 常用獲取元素 Driver 總結(jié)
今天小編就為大家分享一篇關(guān)于Python 常用獲取元素 Driver 總結(jié),具有很好的參考價(jià)值,希望對(duì)大家有所幫助。一起跟隨小編過(guò)來(lái)看看吧2019-11-11Python3使用正則表達(dá)式爬取內(nèi)涵段子示例
這篇文章主要介紹了Python3使用正則表達(dá)式爬取內(nèi)涵段子,涉及Python正則匹配與文件讀寫(xiě)相關(guān)操作技巧,需要的朋友可以參考下2018-04-04Python高級(jí)過(guò)濾器之filter函數(shù)詳解
在Python中,filter()是一個(gè)非常有用的內(nèi)置函數(shù),它能夠根據(jù)指定的函數(shù)來(lái)篩選出可迭代對(duì)象中滿(mǎn)足條件的元素,本文將從入門(mén)到精通,全面介紹filter()函數(shù)的用法和相關(guān)知識(shí)點(diǎn)2023-08-08pycharm下配置pyqt5的教程(anaconda虛擬環(huán)境下+tensorflow)
這篇文章主要介紹了pycharm下配置pyqt5的教程(anaconda虛擬環(huán)境下+tensorflow),本文給大家介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值,需要的朋友可以參考下2020-03-03