堆排序简介
堆排序(Heap Sort),是指利用堆这种数据结构所设计的一种排序算法。
堆排序的基本思想:将待排序的序列构造成一个大顶堆。此时,整个序列的最大值就是堆顶的根结点。将它与末尾元素交换,此时末尾元素就是最大值,然后将剩余的n-1
个序列重新构造成一个堆,这样就会得到n个元素中的次小值。如此反复执行,便能得到一个有序序列。
堆结点的访问
通常堆是通过一维数组来实现的。在数组起始位置为0的情形下:
- 父节点i的左子节点在位置(2*i+1)
- 父节点i的右子节点在位置(2*i+2)
- 子节点i的父节点在位置floor((i-1)/2)
堆排序过程
具体排序过程如下图所示:
算法实现
1 | /** |
算法分析
时间复杂度
由于堆排序对原始记录的排序状态并不敏感,因此它无论是最好、最坏和平均时间复杂度均为$\Theta(nlogn)$
空间复杂度
很明显,其空间复杂度为$\Theta(1)$。
稳定性
由于记录的比较和交换是跳跃式的,所以堆排序是不稳定的。