时间:2021-05-22
本文实例讲述了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//2def 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: breakdef 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 maxElemdata=[-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)-1for 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: breakdef 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相关内容感兴趣的读者可查看本站专题:《Python数据结构与算法教程》、《Python加密解密算法与技巧总结》、《Python编码操作技巧总结》、《Python函数使用技巧总结》、《Python字符串操作技巧汇总》及《Python入门与进阶经典教程》
希望本文所述对大家Python程序设计有所帮助。
声明:本页内容来源网络,仅供用户参考;我单位不保证亦不表示资料全面及准确无误,也不保证亦不表示这些资料为最新信息,如因任何原因,本网内容或者用户因倚赖本网内容造成任何损失或损害,我单位将不会负任何法律责任。如涉及版权问题,请提交至online#300.cn邮箱联系删除。
本文实例讲述了Python排序搜索基本算法之希尔排序。分享给大家供大家参考,具体如下:希尔排序是插入排序的扩展,通过允许非相邻的元素进行交换来提高执行效率。希尔
本文实例讲述了Python实现的堆排序算法。分享给大家供大家参考,具体如下:堆排序(Heapsort)是指利用堆这种数据结构所设计的一种排序算法。堆是一个近似完
本文实例讲述了Python排序搜索基本算法之归并排序。分享给大家供大家参考,具体如下:归并排序最令人兴奋的特点是:不论输入是什么样的,它对N个元素的序列排序所用
本文实例讲述了Python实现堆排序的方法。分享给大家供大家参考,具体如下:堆排序作是基本排序方法的一种,类似于合并排序而不像插入排序,它的运行时间为O(nlo
本文实例讲述了Python排序搜索基本算法之插入排序。分享给大家供大家参考,具体如下:插入排序生活中非常常见,打扑克的时候人的本能就在用插入排序:把抽到的一张插