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

鹏仔微信 15129739599 鹏仔QQ344225443 鹏仔前端 pjxi.com 共享博客 sharedbk.com