当前位置:鱼C工作室 >数据结构和算法 > 查看文章

堆排序 – 数据结构和算法92

堆排序

 

让编程改变世界

Change the world by program


 

堆排序

 

上节课我们介绍的希尔排序是对直接插入排序的改进,而我们这节课谈的堆排序是对选择排序进行改进的排序算法,堆排序算法的时间复杂度和希尔排序是一样的,都是O(nlogn)。

堆排序的话呢,涉及到的数据结构是完全二叉树,或者说完全二叉树正是因为有堆排序这样的高效算法而显得重要!我们来回顾下:

 

小顶堆

小顶堆

大顶堆

大顶堆

 

如图,堆是具有下列性质的完全二叉树:每个结点的值都大于或者等于其左右孩子结点的值,称为大顶堆;或者每个结点的值都小于或者等于其左右孩子结点的值,称为小顶堆。

 

那么从概念我们可以知道,根结点一定是堆中所有结点最大或者最小者,如果按照层序遍历的方式给结点从1开始编号,则结点之间满足如下关系:

堆排序

 

下标i与2i和2i+1是双亲和子女关系。

那么如果把大顶堆和小顶堆用层序遍历存入数组,则一定满足上面的表达式。

 

我们用刚才的图举例说明:

…… 省略,具体请看视频讲解 ……

 

堆排序算法

 

堆排序(Heap Sort)就是利用堆进行排序的算法,它的基本思想是:

将待排序的序列构造成一个大顶堆(或小顶堆)。

此时,整个序列的最大值就是堆顶的根结点。将它移走(就是将其与堆数组的末尾元素交换,此时末尾元素就是最大值)。

然后将剩余的n-1个序列重新构造成一个堆,这样就会得到n个元素中的此大值。

如此反复执行,便能得到一个有序序列了。

 

…… 省略,具体请看视频讲解 ……


为您推荐

报歉!评论已关闭.