堆排序 – 数据结构和算法92
堆排序
让编程改变世界
Change the world by program
堆排序
上节课我们介绍的希尔排序是对直接插入排序的改进，而我们这节课谈的堆排序是对选择排序进行改进的排序算法，堆排序算法的时间复杂度和希尔排序是一样的，都是O（nlogn）。
堆排序的话呢，涉及到的数据结构是完全二叉树，或者说完全二叉树正是因为有堆排序这样的高效算法而显得重要！我们来回顾下：
小顶堆
大顶堆
如图，堆是具有下列性质的完全二叉树：每个结点的值都大于或者等于其左右孩子结点的值，称为大顶堆；或者每个结点的值都小于或者等于其左右孩子结点的值，称为小顶堆。
那么从概念我们可以知道，根结点一定是堆中所有结点最大或者最小者，如果按照层序遍历的方式给结点从1开始编号，则结点之间满足如下关系：
下标i与2i和2i+1是双亲和子女关系。
那么如果把大顶堆和小顶堆用层序遍历存入数组，则一定满足上面的表达式。
我们用刚才的图举例说明：
…… 省略，具体请看视频讲解 ……
堆排序算法
堆排序（Heap Sort）就是利用堆进行排序的算法，它的基本思想是：
将待排序的序列构造成一个大顶堆（或小顶堆）。
此时，整个序列的最大值就是堆顶的根结点。将它移走（就是将其与堆数组的末尾元素交换，此时末尾元素就是最大值）。
然后将剩余的n-1个序列重新构造成一个堆，这样就会得到n个元素中的此大值。
如此反复执行，便能得到一个有序序列了。
…… 省略，具体请看视频讲解 ……
备用视频下载
技术, IT技术, 数据结构和算法, 排序
风险提示及免责条款
市场有风险，投资需谨慎。本文不构成个人投资建议，也未考虑到个别用户特殊的投资目标、财务状况或需要。用户应考虑本文中的任何意见、观点或结论是否符合其特定状况。据此投资，责任自负。
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！
