这篇文章主要介绍了Python排序搜索基本算法之堆排序,结合实例形式详细分析了堆排序的原理、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]</div><p>fixUp函数用于向列表的尾部添加一个新的元素，然后调整成大顶堆；fixDown函数用于取出大顶堆最大的元素后，把列表尾部的元素放到堆顶位置，然后再调整成大顶堆；insert函数是每次插入一个新的元素并调整成为大顶堆；delMax函数把最大的元素返回出来并把剩下的元素调整成为大顶堆。</p><p>输出如下：</p><div class="gaodaimacode"><pre class="prettyprint linenums"> [-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]1: l[1]<strong style="color:transparent">来源gao@daima#com搞(%代@#码@网</strong>,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.gaodaima.com/aideddesign/paixu_ys
更多关于Python相关内容感兴趣的读者可查看本站专题：《Python数据结构与算法教程》、《Python加密解密算法与技巧总结》、《Python编码操作技巧总结》、《Python函数使用技巧总结》、《Python字符串操作技巧汇总》及《Python入门与进阶经典教程》
希望本文所述对大家Python程序设计有所帮助。
以上就是Python排序搜索基本算法之堆排序实例详解的详细内容，更多请关注gaodaima搞代码网其它相关文章！
搞代码网（gaodaima.com）提供的所有资源部分来自互联网，如果有侵犯您的版权或其他权益，请说明详细缘由并提供版权或权益证明然后发送到邮箱[email protected]，我们会在看到邮件的第一时间内为您处理，或直接联系QQ：872152909。本网站采用BY-NC-SA协议进行授权
转载请注明原文链接：Python排序搜索基本算法之堆排序实例详解
转载请注明原文链接：Python排序搜索基本算法之堆排序实例详解
