Python 堆排序

原理

堆排序(Heapsort)是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于(或者大于)它的父节点。

步骤

创建最大堆:将堆所有数据重新排序，使其成为最大堆

最大堆调整:作用是保持最大堆的性质，是创建最大堆的核心子程序

堆排序:移除位在第一个数据的根节点，并做最大堆调整的递归运算

代码

defheap_sort(list):

#创建最大堆

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

#最大堆调整

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

以上内容为大家介绍了Python堆排序，希望对大家有所帮助，如果想要了解更多Python相关知识，请关注IT培训机构:千锋教育。

声明：本站部分稿件版权来源于网络，如有侵犯版权，请及时联系我们。