堆排序动画演示，Python代码演示，看不懂你砍我！

内容简介：堆排序动画演示，Python代码演示，看不懂你砍我！

堆排序，一个经典的算法，我们先看动画演示吧：

数组: [6,5,3,1,8,7,2]

首先，这个数组不是有序的，并且，不是每个根节点都大于子节点，所以，如果我们第一步是让这颗树变得规范一些：即让每个父节点都大于任意子节点（堆有序）

如何实现呢？其实，我们要做的就是找到所有的父节点，然后逐个遍历，让这些有子节点的父节点都变得根节点大于任意节点就好了，看图，

到现在为止，我们就让我们的堆有序了，然后，就是给堆进行排序了，从现在的途中，我们可以很容易看到，根节点0是这里边最大的元素，所以，我们就已经找到最大元素了，那么我们可以做这儿一个操作：讲第一个元素和最后一个元素互换，这样最后一个元素就是最大的了，我们就不用再比较它了

然后，我们就到了我们递归的部分，剩下的部分，我们只需要保证每个根节点都大于任意子节点就好了，这样排序之后，我们就再次让根节点0编程剩下的所有元素中最大的了

然后，我们再把第0个元素和最后一个元素互换

然后，就是继续重复上边的过程……

具体的 python 代码:

#-*-coding:utf-8-*-
def heap_sort(ary) :
    n = len(ary)
    print 'length of arr is :',n
    first = int(n/2-1)       #最后一个非叶子节点
    for start in range(first,-1,-1) :     #构造大根堆
        max_heapify(ary,start,n-1)
    print '第一次排序之后，应该是每个父节点都大于子节点',ary
    for end in range(n-1,0,-1):           #堆排，将大根堆转换成有序数组
        ary[end],ary[0] = ary[0],ary[end]
        max_heapify(ary,0,end-1)
    return ary
#最大堆调整：将堆的末端子节点作调整，使得子节点永远小于父节点
#start为当前需要调整最大堆的位置，end为调整边界
def max_heapify(ary,start,end):
    root = start
    while True :
        child = root*2 +1               #调整节点的子节点
        if child > end : break
        if child+1 <= end and ary[child] < ary[child+1] :
            child = child+1             #取较大的子节点
        if ary[root] < ary[child] :     #较大的子节点成为父节点
            ary[root],ary[child] = ary[child],ary[root]     #交换
            root = child
        else :
            break
 
if __name__ == '__main__':
    array=[6,5,3,1,8,7,2,4]
 
    print heap_sort(array)

参考资料：https://zh.wikipedia.org/zh/%E5%A0%86%E6%8E%92%E5%BA%8F#Python.E8.AF.AD.E8.A8.80

以上就是本文的全部内容，希望本文的内容对大家的学习或者工作能带来一定的帮助，也希望大家多多支持 码农网

查看所有标签

本站部分资源来源于网络，本站转载出于传递更多信息之目的，版权归原作者或者来源机构所有，如转载稿涉及版权问题，请联系我们。