堆排序
堆排序
堆排序(Heapsort) 是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构,并同时满足堆积的性质:即子结点的键值或索引总是小于(或者大于)它的父节点。
堆排序可以说是一种利用堆的概念来排序的选择排序。分为两种方法:
- 大顶堆:每个节点的值都大于或等于其子节点的值,在堆排序算法中用于升序排列.
- 小顶堆:每个节点的值都小于或等于其子节点的值,在堆排序算法中用于降序排列.
如下图:
因为我们常用数组来存储完全二叉树,所以我们也可以用数组来存储堆。
堆在数组中的存储图如下:
由上图我们可以看出对于堆中元素下标为i的点:
2*i+1为它的左子节点
2*i+2为它的右子节点
-
算法原理
堆排序的算法原理:
创建一个堆 H[0……n-1].
把堆首(最大值)和堆尾互换.
把堆的尺寸缩小 1,并调用 shift_down(0),目的是把新的数组顶端数据调整到相应位置.
重复步骤2,直到堆的尺寸为 1.
堆排序算法实现:
1 |
|
运行结果:
1 |
|