堆排序(HeapSort)

作者: admin 分类: 算法 发布时间: 2013-02-16 13:23 ė1,972 浏览数 6没有评论
文章转自王牌软件
站长推荐:NSetup一键部署软件
一键式完成美化安装包制作,自动增量升级,数据统计,数字签名。应对各种复杂场景,脚本模块化拆分,常规复杂的脚本代码,图形化设置。无需专业的研发经验,轻松完成项目部署。(www.nsetup.cn)

本文主要介绍堆排序算法(HeapSort),堆排序像合并排序而不像插入排序,堆排序的运行时间为O(nlgn);像插入排序而不像合并排序,它是一种原地(in place)排序算法。在任何时候,数组中只有常数个元素存储在输入数组以外,这样,堆排序就把插入排序和合并排序的优点结合起来。

       堆排序还引入了另外一种算法设计技术,利用某种数据结构(在此算法中为“堆”)来管理算法执行中的信息。堆数据结构不只在堆排序算法中有用,还可以构成一个有效的优先队列。堆数据结构是一种数组对象,它可以被视为一颗完全二叉树,树种每个结点与数组中存放该结点值的那个元素对应。树的每一层都是填满的,最后一层除外(最后一层从一个结点的左子树开始填)。

 一、堆排序算法原理

       开始时,堆排序算法先用BuildMaxHeap()函数将n个元素的输入数组array[0...n-1]建造成一个大顶堆。因为数组中最大元素在对应堆树的根A[1],所以可以通过把它与A[n]互换来达到最终正确的位置。现在如果从堆中“去掉”结点n(通过减小堆大小HeapSize),可以很容易的将这一数组转换成一个最大堆。原来根的子女仍是最大堆,而新的堆元素可能违背了最大堆性质。这时调用MaxHeapify(array ,temp)函数就可以保持这一性质,由此在A[1...n-1]中构造出最大堆。堆排序算法不断重复这个过程,堆的大小从n-1一直降到2。

二、堆排序算法的实现

运行结果:
 

  

三、堆排序算法分析

       堆排序算法集中的插入排序和合并排序的优点,既可以原地排序又有一个较优异的复杂性O(nlgn),而且所采用的堆数据结构还有一个广泛的应用,作为高效的优先级队列(Priority Queue)。详细应用讲解可以参考《算法导论》原书第二版P80。

       另外,须知在实际应用中,快速排序的一个好的实现往往由于堆排序。


 



只回答业务咨询点击这里给我发消息 点击这里给我发消息

王牌软件,兼职软件设计,软件修改,毕业设计。

本文出自 王牌软件,转载时请注明出处及相应链接。

本文永久链接: http://www.softwareace.cn/?p=170

0

发表评论

电子邮件地址不会被公开。 必填项已用*标注

您可以使用这些HTML标签和属性: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code class="" title="" data-url=""> <del datetime=""> <em> <i> <q cite=""> <strike> <strong> <pre class="" title="" data-url=""> <span class="" title="" data-url="">


Ɣ回顶部

无觅相关文章插件,快速提升流量