淺談插入排序算法在Python程序中的實(shí)現(xiàn)及簡(jiǎn)單改進(jìn)
Python實(shí)現(xiàn)插入排序的一般范例為:
#coding=cp936 #coding=cp936 #插入排序算法 def InsertionSort(A): for j in range(1,len(A)): key = A[j] i = j-1 #向前查找插入位置 while i>=0 and A[i]>key: A[i+1] = A[i] i = i-1 A[i+1] = key #初始化輸入數(shù)據(jù) A = [] input = raw_input('please input some numbers:') #輸入逗號(hào)分隔整數(shù)列 如:7,6,5,1,8,34 for item in input.split(','): A.append(int(item)) InsertionSort(A)#插入排序 print A
插入算法的原理是:當(dāng)前元素和已經(jīng)排序好的部分比較,滿足條件時(shí)插入,插入點(diǎn)之后的元素全部往后移。
然而,我也正是受這個(gè)描述的誤導(dǎo),在實(shí)現(xiàn)的時(shí)候走了一些彎路。比如有以下列表:
test = [2, 5, 11, 21, 10, 18, 24]
比如當(dāng)前元素是10,我在開最初的實(shí)現(xiàn)思路是從列表的第一個(gè)元素開始,一直比較到元素11才找到合適位置.這樣做最終是可以實(shí)現(xiàn)排序的,但是有一個(gè)問題,就是當(dāng)我把10插入11的位置之后,11和21都需要往后移,這又需要另一個(gè)循環(huán),實(shí)現(xiàn)如下:
def insertSort(sort_list): list_length = len(sort_list) if list_length < 2 : return sort_list for i in range(1,list_length): key = sort_list[i] j = 0 while j < i: if sort_list[j] > key: for k in range(i,j,-1): sort_list[k] = sort_list[k-1] sort_list[j] = key break j += 1 return sort_list
首先,引入了三個(gè)循環(huán)變量以及三層循環(huán),效率較低;其次是代碼結(jié)構(gòu)會(huì)比較混亂,需要改進(jìn)。
后來我想能不能比較完一個(gè)元素就把它移到合適的位置,好如去超市買水果,手里拿到不合適的,總會(huì)直接把它放到一邊,不會(huì)再碰它。具體到算法實(shí)現(xiàn),還用上面的列表舉例,當(dāng)前元素是10,先跟相鄰的21比較,發(fā)現(xiàn)21比10大,則21往后移動(dòng)一位,即移到10所在位置;然后10和11比較,又會(huì)把11往后移動(dòng)一位;在比較到元素5時(shí),發(fā)現(xiàn)已經(jīng)找到了10應(yīng)該存放的位置,而此時(shí)移動(dòng)也隨之完成。
代碼實(shí)現(xiàn)如下:
def insertSort(sort_list): list_length = len(sort_list) if list_length < 2 : return sort_list for i in range(1,list_length): key = sort_list[i] j = i - 1 while j >=0 and sort_list[j] > key: sort_list[j+1] = sort_list[j] j -= 1 sort_list[j+1] = key return sort_list
孰優(yōu)孰劣,大家對(duì)比便知。
相關(guān)文章
python虛擬機(jī)之描述器實(shí)現(xiàn)原理與源碼分析
在本篇文章當(dāng)中主要給大家介紹描述器背后的實(shí)現(xiàn)原理,通過分析?cpython對(duì)應(yīng)的源代碼了解與描述器相關(guān)的字節(jié)碼的指令,我們就可以真正了解到描述器背后的原理,需要的朋友可以參考下2023-05-05Python?pyecharts案例超市4年數(shù)據(jù)可視化分析
這篇文章主要介紹了Python?pyecharts案例超市4年數(shù)據(jù)可視化分析,文章圍繞主題展開詳細(xì)的內(nèi)容介紹,具有一定的參考價(jià)值,需要的小伙伴可以參考一下2022-08-08pyshp創(chuàng)建shp點(diǎn)文件的方法
今天小編就為大家分享一篇pyshp創(chuàng)建shp點(diǎn)文件的方法,具有很好的參考價(jià)值,希望對(duì)大家有所幫助。一起跟隨小編過來看看吧2018-12-12Python IDE PyCharm的基本快捷鍵和配置簡(jiǎn)介
這篇文章主要介紹了Python IDE PyCharm的基本快捷鍵和配置簡(jiǎn)介,PyCharm為一個(gè)收費(fèi)的軟件,需要的朋友可以參考下2015-11-11python 標(biāo)準(zhǔn)差計(jì)算的實(shí)現(xiàn)(std)
這篇文章主要介紹了python 標(biāo)準(zhǔn)差計(jì)算的實(shí)現(xiàn)(std),文中通過示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2019-07-07