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培训机构:千锋教育。

猜你喜欢LIKE
相关推荐HOT
更多>>
python函数中使用for循环
python函数中使用for循环1、在for循环中使用函数需要更长的执行时间,因为每次迭代都会调用该函数。2、如果for循环是在函数内部实现的,那么该...详情>>
2023-11-14 13:53:34
python3.1版本的特性有哪些
python3.1中的特性有哪些1、千位数格式化,可以在使用字符串格式化函数时直接完成。在格式化大数时,通常是每三位数放置逗号,使数字更易读(例...详情>>
2023-11-14 13:18:27
python__new__()和__init__()有什么区别?
在python中,__new__()不是一定要有,只有继承自object的类才有,该方法可以return父类(通过super(当前类名,cls).__new__())出来的实例,或者直...详情>>
2023-11-14 12:38:55
pythonwheel是什么
python的第一个主流打包格式是.egg文件,现在大家庭中又有了一个叫做Wheel(*.whl)的新成员。wheel“被设计成包含PEP376兼容安装(一种非常接近于...详情>>
2023-11-14 11:30:39热门推荐
技术干货






