Python 堆排序

原理

堆排序(Heapsort)是指利用堆這種數(shù)據(jù)結(jié)構(gòu)所設(shè)計的一種排序算法。堆積是一個近似完全二叉樹的結(jié)構(gòu)，并同時滿足堆積的性質(zhì)：即子結(jié)點的鍵值或索引總是小于(或者大于)它的父節(jié)點。

步驟

創(chuàng)建最大堆:將堆所有數(shù)據(jù)重新排序，使其成為最大堆

最大堆調(diào)整:作用是保持最大堆的性質(zhì)，是創(chuàng)建最大堆的核心子程序

堆排序:移除位在第一個數(shù)據(jù)的根節(jié)點，并做最大堆調(diào)整的遞歸運算

代碼

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堆排序，希望對大家有所幫助，如果想要了解更多Python相關(guān)知識，請關(guān)注IT培訓(xùn)機構(gòu):千鋒教育。