Python排序搜索基本算法之堆排序实例详解
作者:littlethunder 发布时间:2021-07-10 12:35:30
标签:Python,算法,堆排序
本文实例讲述了Python排序搜索基本算法之堆排序。分享给大家供大家参考,具体如下:
堆是一种完全二叉树,堆排序是一种树形选择排序,利用了大顶堆堆顶元素最大的特点,不断取出最大元素,并调整使剩下的元素还是大顶堆,依次取出最大元素就是排好序的列表。举例如下,把序列[26,5,77,1,61,11,59,15,48,19]排序,如下:
基于堆的优先队列算法代码如下:
def fixUp(a): #在堆尾加入新元素,fixUp恢复堆的条件
k=len(a)-1
while k>1 and a[k//2]<a[k]:
a[k//2],a[k]=a[k],a[k//2]
k=k//2
def fixDown(a): #取a[1]返回的值,然后把a[N]移到a[1],fixDown来恢复堆的条件
k=1
N=len(a)-1
while 2*k<=N:
j=2*k
if j<N and a[j]<a[j+1]:
j+=1
if a[k]<a[j]:
a[k],a[j]=a[j],a[k]
k=j
else:
break
def insert(a,elem):
a.append(elem)
fixUp(a)
def delMax(a):
maxElem=a[1]
N=len(a)
if N<=1:
print('There\'s none element in the list')
return -1
if N==2:
return a[1]
else:
a[1]=a.pop()
fixDown(a)
return maxElem
data=[-1,] #第一个元素不用,占位
insert(data,26)
insert(data,5)
insert(data,77)
insert(data,1)
insert(data,61)
insert(data,11)
insert(data,59)
insert(data,15)
insert(data,48)
insert(data,19)
result=[]
N=len(data)-1
for i in range(N):
print(data)
result.append(delMax(data))
print(result)
fixUp函数用于向列表的尾部添加一个新的元素,然后调整成大顶堆;fixDown函数用于取出大顶堆最大的元素后,把列表尾部的元素放到堆顶位置,然后再调整成大顶堆;insert函数是每次插入一个新的元素并调整成为大顶堆;delMax函数把最大的元素返回出来并把剩下的元素调整成为大顶堆。
输出如下:
[-1, 77, 61, 59, 48, 19, 11, 26, 1, 15, 5]
[-1, 61, 48, 59, 15, 19, 11, 26, 1, 5]
[-1, 59, 48, 26, 15, 19, 11, 5, 1]
[-1, 48, 19, 26, 15, 1, 11, 5]
[-1, 26, 19, 11, 15, 1, 5]
[-1, 19, 15, 11, 5, 1]
[-1, 15, 5, 11, 1]
[-1, 11, 5, 1]
[-1, 5, 1]
[-1, 1]
[77, 61, 59, 48, 26, 19, 15, 11, 5, 1]
前面的输出是不断取出最大元素后的大顶堆,由于是完全二叉树,根据列表可以自己写出大顶堆的树形结构,就不在这里赘述,最后一行是排好序的列表。
下面是堆排序算法,代码如下:
def fixDown(a,k,n): #自顶向下堆化,从k开始堆化
N=n-1
while 2*k<=N:
j=2*k
if j<N and a[j]<a[j+1]: #选出左右孩子节点中更大的那个
j+=1
if a[k]<a[j]:
a[k],a[j]=a[j],a[k]
k=j
else:
break
def heapSort(l):
n=len(l)-1
for i in range(n//2,0,-1):
fixDown(l,i,len(l))
while n>1:
l[1],l[n]=l[n],l[1]
fixDown(l,1,n)
n-=1
return l[1:]
l=[-1,26,5,77,1,61,11,59,15,48,19] #第一个元素不用,占位
res=heapSort(l)
print(res)
输出如下:
[1, 5, 11, 15, 19, 26, 48, 59, 61, 77]
PS:这里再为大家推荐一款关于排序的演示工具供大家参考:
在线动画演示插入/选择/冒泡/归并/希尔/快速排序算法过程工具:
http://tools.jb51.net/aideddesign/paixu_ys
希望本文所述对大家Python程序设计有所帮助。
来源:http://blog.csdn.net/littlethunder/article/details/23877545
0
投稿
猜你喜欢
- 今天在GOOGLE上查图片资料,这一幕真让我纠结啊:使用【向前】【向后】这种说法,就默认了有一个对比坐标,那就是当前显示的4张缩略图。点击【
- 目录前言1. 效果图2. 原理3. 源码3.1 Numpy实现傅里叶变换3.2 OpenCV实现傅里叶变换3.3 HPF or LPF?参考
- 一年中秋至 又见圆月时导语假设农历八月十五,程序员错过了今年的中秋圆月。▼程序员的苦只有他们寄几知道bug,bug,bug,bug,bug,
- 今天是边复习边创作博客的第三天,我今年大二,我们专业开的有这门课程,因为喜欢所以更加认真学习,本以为没人看呢,看了后台浏览量让我更加认真创作
- 本文通过一个详细的例子,来阐述了在线编辑XML文档数据的方法。由于Netscape对XML的支持比较弱,因此,要实现跨平台的数据交换,数据的
- django中有自带的分页模块Paginator,想Paginator提供对象的列表,就可以提供每一页上对象的方法。这里的话不讲解Pagin
- 作者:AngelGavin 出处:CSDNInternet Explorer 5.0 对 XML 提供哪个级别的支持?Inter
- 前言人脸识别在LWF(Labeled Faces in the Wild)数据集上人脸识别率现在已经99.7%以上,这个识别率确实非常高了,
- 用系统\administrators可以登录,在安全性用户列表中,修改sa属性时系统提示: 属性IsLocked不可用于登录"[s
- 本文实例为大家分享了python实现支付宝当面付示的具体代码,供大家参考,具体内容如下一、配置信息准备登录蚂蚁金服开放平台:https://
- 本文为大家分享了pygame游戏之旅的第10篇,供大家参考,具体内容如下通过获取鼠标的位置然后进行高亮显示:mouse =pygame.mo
- 如何使用Index Server建立一个网站导航地图?程序代码如下:<html><head><title>asp教程之网站导航 -
- 遇到那种有很多图的微信公众号文章咋办?一个一个存很麻烦,应朋友的要求自己写了个爬虫。2.0版本完成了!完善了生成pdf的功能,可根据图片比例
- 等啊等,约会都回来了,终于等到了Google放出今年的情人节Logo,原本下午四点就可以上线的这篇文章,为了等待Google谷歌美国总部的那
- 发现pyautocad模块:可以用python控制autocad的包。今天把文档中的重点内容摘录出来,以后绘图、计算大工程量、或者识别施工图
- 实际效果:假设给定目录"/media/data/programmer/project/python" ,备份路径&quo
- 编写Python代码,大家都需要遵循PEP8,因此在pycharm中,如何设置每行最大长度限制,成为了一个小的知识盲点,在这里做一下记录,方
- 查找资料,基本上判断python对象是否为可调用的函数,有三种方法使用内置的callable函数callable(func)用于检查对象是否
- 用 docx 模块读取 Worddocx 安装cmd 中输入pip install python-docx 即可安装 docx 模块docx
- 实现思路将视频(MP4 等)转换为 M3U8 视频的服务,可以按照以下步骤进行操作:将视频(MP4 等)转换为 M3U8:在服务中,使用适当