原理
堆排序(Heapsort)是指利用堆這種數(shù)據(jù)結(jié)構(gòu)所設(shè)計(jì)的一種排序算法。堆積是一個(gè)近似完全二叉樹(shù)的結(jié)構(gòu)，并同時(shí)滿足堆積的性質(zhì)：即子結(jié)點(diǎn)的鍵值或索引總是小于(或者大于)它的父節(jié)點(diǎn)。
步驟
創(chuàng)建最大堆:將堆所有數(shù)據(jù)重新排序，使其成為最大堆
最大堆調(diào)整:作用是保持最大堆的性質(zhì)，是創(chuàng)建最大堆的核心子程序
堆排序:移除位在第一個(gè)數(shù)據(jù)的根節(jié)點(diǎn)，并做最大堆調(diào)整的遞歸運(yùn)算
代碼
defheap_sort(list):
#創(chuàng)建最大堆
forstartinrange((len(list)-2)//2,-1,-1):
sift_down(list,start,len(list)-1)
#堆排序
forendinrange(len(list)-1,0,-1):
list[0],list[end]=list[end],list[0]
sift_down(list,0,end-1)
returnlist
#最大堆調(diào)整
defsift_down(lst,start,end):
root=start
whileTrue:
child=2*root+1
ifchild>end:
break
ifchild+1<=endandlst[child] child+=1 iflst[root] lst[root],lst[child]=lst[child],lst[root] root=child else: break 以上內(nèi)容為大家介紹了Python堆排序，希望對(duì)大家有所幫助，如果想要了解更多Python相關(guān)知識(shí)，請(qǐng)關(guān)注IT培訓(xùn)機(jī)構(gòu):千鋒教育。
京公網(wǎng)安備 11010802030320號(hào)