一、堆排序思想 (要和shell排序区别)
堆,是一棵完全二叉树,(完全二叉树概念:只有最后两层可以是业界点,而且最底层的叶节点都在左侧,图在上一篇日志上有)
堆可以用数组来描述,在排序中强调的是 大根堆(最大值在树根),将大根堆的的根部值 和 无序数组的最后一个数交换,然后重新排序新的无序堆为 大根堆。
具体排序思想:将待排序区分为无序区和有序区,无序区在前,有序区在后。未排序前无序区为整个待排序区间,没有有序区。
排序的过程是,不断地将无序区构造成一个大根堆,这样无序区中的最大元素便被放置在了数组的最前面即根的位置,然后将无序区的第一个元素与最后一个元素交换,此动作将无序区的长度缩小一,将有序区的长度扩大一,即有序区前进一,无序区向前退一。然后将新的无序区(由于根节点的变化,此时很可能已经不是大根堆)重新调整为大根堆,等待下一次的交换。如此往复,不断地将无序区的最大元素添加到有序区的前面,同时缩小无序区,直到有序区占满待排序区为止。
这样,还剩下两个问题: 1.如何将一个交换后的无序区调整为大根堆; 2.如何在排序之前建立那个初始的大根堆。而第二个问题是可以通过第一个问题的解决而解决的。
1.如何将一个交换后的无序区调整为大根堆?
由于进行元素交换前,无序区是一个大根堆,即左子树和右子树都是大根堆,所以根节点变化后左右子树仍然都是大根堆,无序区里的最大元素一定在新根节点、左右子树的根节点这三个结点里。先存储新的根节点的值以待后用。如果新的根结点最大,说明已经是大根堆,调整完毕;
否则比较左右子树根节点,找出较大的,它是无序区现存的最大元素,应该作为新的大根堆中的根,所以将此节点上调至根节点位置,接下来就只需要调整此结点原来所在的子树为大根堆即可(因为大根堆对左右子树之间元素的大小关系没有要求!)。
2..那么如何利用此过程建立初始大根堆呢?
若数组下标范围为0~n,考虑到单独一个元素是大根堆,则从下标[n/2]开始的元素均为大根堆(叶节点)。于是只要从[n/2]-1开始,向前依次构造大根堆,这样就能保证,构造到某个节点时,它的左右子树都已经是大根堆(这就可以调用我们上面讨论的调整为大根堆的方法了)。一直到下标为0的结点,就完成了初始大根堆的建立。 堆排序用到的函数有两个:1个将左右子树都为大根堆的完全二叉树调整为大根堆的调整函数;1个反复调用此调整函数来进行排序的排序函数。
输入:50,435,6437,768,8,45,567,1435;
从第length/2开始构造,即第4个768开始构造大根堆
分享到:
相关推荐
堆排序--大顶堆排序
C语言版的排序方法---堆排序,非常有用的代码,可以实际中使用。
常用的排序算法--堆排序,通过创建堆的方法进行排序
详解Java常用排序算法-堆排序
实现以下常用的内部排序算法并进行性能比较:"直接插入排序"," 折半插入排序"," 2—路插入排序"," 表插入排序"," 希尔排序"," 起泡排序"," 快速排序"," 简单选择排序"," 树形选择排序"," 堆排序"," 归并排序"," 链式...
(1) 完成5种常用内部排序算法的演示,5种排序算法为:快速排序,直接插入排序,选择排序,堆排序,希尔排序; (2) 待排序元素为整数,排序序列存储在数据文件中,要求排序元素不少于30个; (3) 演示程序开始,...
多线程实现排序算法的比较:希尔排序、快速排序、堆排序。用java语言实现,很经典,需要的可以下载看看!
c语言实现堆排序。代码实现的是建立大根堆
直接插入排序 选择排序 堆排序 归并排序 快速排序 冒泡排序等七种排序方法
最快的排序算法 谁才是最强的排序算法:快速排序-归并排序-堆排序,排序算法数据结构
Java代码-排序-直接插入排序、希尔排序、直接选择排序、冒泡排序、堆排序、快速排序、归并排序中部分排序以及算法-贪心法,大家可以将源码下载下来进行学习,附带着注释和解释,有不理解的可以找博主一起探讨,共同...
该资源提供了Java中实现堆排序的全面指南。文档中涵盖了堆排序的基本概念,包括如何对数组进行排序以及如何在Java中实现堆排序。此外,文档还包括一个逐步指南,介绍了如何在Java中实现堆排序,包括详细的代码示例和...
自己看书时写的排序算法:堆排序 CPP文件
希尔排序,堆排序,快速排序,简单选择排序,插入排序,冒泡排序
8.12-8.19_冒泡_选择_插入_希尔_快速_归并_基数_堆排序_排序算法Swift代码及UI演示
7大排序算法(快速排序,冒泡排序,选择排序,归并排序,插入排序,希尔排序,堆排序)实现源码
直接插入排序 冒泡排序 快速排序 直接选择排序 堆排序 二路归并排序 C#源代码 使用C#实现的数据结构中的排序算法
堆排序-flash演示 可自己输入数据............
讲解了选择排序的基本原理,并用C++实现了简单选择排序,和堆排序算法,并进行了算法复杂度的分析。
这是我的博客 《漫谈经典排序算法:一、从简单选择排序到堆排序的深度解析》中涉及到的源代码,详细解析请关注本人博客 http://blog.csdn.net/Touch_2011