常用12大排序算法之七:选择排序之堆排序(最小堆降序排序+最大堆升序排序)

2017-04-22 20:18 阅读 4,180 次 评论 0 条

1.堆排序的基础知识

(1)堆分类:

a.最大堆:所有节点的子节点比其自身小的堆。

b.最小堆:所有节点的子节点比其自身大的堆。

(2)堆排序简介

堆分为最大堆和最小堆,其实就是完全二叉树。最大堆要求节点的元素都要大于其孩子,最小堆要求节点元素都小于其左右孩子,两者对左右孩子的大小关系不做任何要求,其实很好理解。

根据上面的定义,我们可以得知,处于最大堆的根节点的元素一定是这个堆中的最大值。其实我们的堆排序算法就是抓住了堆的这一特点,每次都取堆顶的元素,将其放在序列最后面,然后将剩余的元素重新调整为最大堆,依次类推,最终得到排序的序列。

或者说,堆排序将所有的待排序数据分为两部分,无序区和有序区。无序区也就是前面的最大堆数据,有序区是每次将堆顶元素放到最后排列而成的序列。每一次堆排序过程都是有序区元素个数增加,无序区元素个数减少的过程。当无序区元素个数为1时,堆排序就完成了。
本质上讲,堆排序是一种选择排序,每次都选择堆中最大的元素进行排序。只不过堆排序选择元素的方法更为先进,时间复杂度更低,效率更高。

(3)堆排序基本思想

利用大顶堆(小顶堆)堆顶记录的是最大关键字(最小关键字)这一特性,使得每次从无序中选择最大记录(最小记录)变得简单。其基本思想为(大顶堆):

(1)将初始待排序关键字序列(R1,R2....Rn)构建成大顶堆,此堆为初始的无须区;

(2)将堆顶元素R[1]与最后一个元素R[n]交换,此时得到新的无序区(R1,R2,......Rn-1)和新的有序区(Rn),且满足R[1,2...n-1]<=R[n];

(3)由于交换后新的堆顶R[1]可能违反堆的性质,因此需要对当前无序区(R1,R2,......Rn-1)调整为新堆,然后再次将R[1]与无序区最后一个元素交换,得到新的无序区(R1,R2....Rn-2)和新的有序区(Rn-1,Rn)。不断重复此过程直到有序区的元素个数为n-1,则整个排序过程完成。

2.堆排序的步骤

(1)首先从第一个非叶子节点开始,比较当前节点和其孩子节点,将最大的元素放在当前节点,交换当前节点和最大节点元素;

(2)将当前元素前面所有的元素都进行1的过程,这样就生成了最大堆;

(3)将堆顶元素和最后一个元素交换,列表长度减1。由此无序区减1,有序区加1;

(4)剩余元素重新调整建堆;

(5)继续3和4,直到所有元素都完成排序。

3.堆排序举例

给定一个整形数组a[]={16,7,3,20,17,8},对其进行堆排序。

(1)首先根据该数组元素构建一个完全二叉树,得到如下结果:

堆排序-1

(2)然后需要构造初始堆,则从最后一个非叶节点开始调整,调整过程如下:

堆排序-2

(3)20和16交换后导致16不满足堆的性质,因此需重新调整,结果如下:

堆排序-3

(4)这样就得到了初始堆:即每次调整都是从父节点、左孩子节点、右孩子节点三者中选择最大者跟父节点进行交换(交换之后可能造成被交换的孩子节点不满足堆的性质,因此每次交换之后要重新对被交换的孩子节点进行调整)。有了初始堆之后就可以进行排序了。

堆排序-4 堆排序-5

(5)此时3位于堆顶不满堆的性质,则需调整继续调整,结果如下:

堆排序-6

这样整个区间便已经有序了。

 

4.堆排序算法分析

从上述过程可知,堆排序其实也是一种选择排序,是一种树形选择排序。只不过直接选择排序中,为了从R[1...n]中选择最大记录,需比较n-1次,然后从R[1...n-2]中选择最大记录需比较n-2次。

事实上这n-2次比较中有很多已经在前面的n-1次比较中已经做过,而树形选择排序恰好利用树形的特点保存了部分前面的比较结果,因此可以减少比较次数。

对于n个关键字序列,最坏情况下每个节点需比较log2(n)次,因此其最坏情况下时间复杂度为nlogn。堆排序为不稳定排序,不适合记录较少的排序。

 

5.堆排序算法C语言源代码

(1)第一种方案:第1部分

(1)第一种方案:第2部分

(1)第一种方案:第3部分

 (2)第二种方案

6.堆排序算法C++源代码

 

版权声明:本文著作权归原作者所有,欢迎分享本文,谢谢支持!
转载请注明:常用12大排序算法之七:选择排序之堆排序(最小堆降序排序+最大堆升序排序) | 算法君

发表评论


表情