首页 » python » 正文

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

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

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

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

2.001

 

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

2.0022.0032.0042.005

2.006 2.007 2.008 2.009 2.010

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

2.012 2.013

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

2.014 2.015 2.016 2.017 2.018 2.019 2.020 2.021

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

2.022 2.023

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

具体的python代码:

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

发表评论