Python排序搜索基本算法之堆排序实例详解
作者:littlethunder 时间:2021-07-10 12:35:30
本文实例讲述了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
标签:Python,算法,堆排序
![](/images/zang.png)
![](/images/jiucuo.png)
猜你喜欢
使用Python自动生成HTML的方法示例
2022-08-12 12:12:18
keras在构建LSTM模型时对变长序列的处理操作
2021-12-06 19:17:31
![](https://img.aspxhome.com/file/2023/1/92481_0s.jpg)
不要跳转或刷新 实现网页区域选择显示
2010-07-02 16:25:00
使用 Python 遍历目录树的方法
2021-09-21 22:19:32
ASP:判断访问是否来自搜索引擎的函数
2008-03-12 11:39:00
ImageMagicK convert crop参数说明
2008-10-21 12:46:00
详解Python3定时器任务代码
2023-10-15 14:50:26
python爬虫开发之urllib模块详细使用方法与实例全解
2021-02-24 04:52:42
好用的Python编辑器WingIDE的使用经验总结
2022-01-15 06:23:10
![](https://img.aspxhome.com/file/2023/0/100290_0s.png)
利用python实现汉诺塔游戏
2021-02-19 03:03:45
![](https://img.aspxhome.com/file/2023/3/87783_0s.jpg)
python scipy.misc.imsave()函数的用法说明
2022-11-01 13:04:24
快速掌握 Mysql数据库对文件操作的封装
2009-02-23 17:37:00
SQL学习笔记八 索引,表连接,子查询,ROW_NUMBER
2011-09-30 11:18:24
python如何实现excel数据添加到mongodb
2023-05-05 17:23:18
在Python中的Django框架中进行字符串翻译
2022-11-04 09:39:03
如何将服务器端变量转换为客户端的变量?
2009-12-03 19:54:00
如何给windows设置定时任务并运行python脚本
2023-09-18 13:40:19
![](https://img.aspxhome.com/file/2023/8/76928_0s.jpg)
简单方法实现网页自动适应任何分辨率任何窗口大小
2008-09-13 19:28:00
了解ASP的基本语法和变量
2008-01-16 13:03:00
pandas和spark dataframe互相转换实例详解
2022-12-12 20:26:38