堆排序
堆排序简介
堆
– 完全二叉树
– 父节点的值 >= 子节点(大根堆)/ 父节点的值 <= 子节点(小根堆)
堆排序
- 构造一个大根堆/小根堆
- 取出堆顶元素(最大值/最小值)
- 将剩下的元素再构建一个大根堆/小根堆,取堆顶元素(将剩下的元素取最大值/最小值)
- 重复以上操作,直到取完堆中元素
- 获得一个有序的序列
– 实质:利用完全二叉树中父节点与子节点之间的内在关系来排序
如何实现堆排序
- 如何构建堆:如何由无序序列构建成堆?
- 如何调整堆:如何在输出堆顶元素后,调整剩余元素?
– 构建堆
– 堆实质上是一个线性表,可以使用顺序存储(数组)- 从完全二叉树的最后一个非叶子节点(序号 i = N / 2 , i 取整 )开始,即由N个元素组成的无序序列,从第 N / 2 个元素开始调整
- 再以 N / 2 – 1 的节点为根的二叉树开始调整
- 再以 N / 2 – 2 的节点为根的二叉树开始调整
- 再以 N / 2 – 3 的节点为根的二叉树开始调整
– 调整堆
– 小根堆调整 - 取出堆顶元素后,以堆中$\color{red}{最后一个元素代替堆顶元素}$
- 将根节点值与左右子树的根节点值进行比较,并与其中$\color{red}{较小者}$进行交换
- 重复上述操作,直至叶子节点,将得到新的堆,这个从堆顶到叶子节点的操作,称$\color{red}{筛选/调整}$
– 大根堆调整 - 取出堆顶元素后,以堆中$\color{red}{最后一个元素代替堆顶元素}$
- 将根节点值与左右子树的根节点值进行比较,并与其中$\color{red}{较大者}$进行交换
- 重复上述操作,直至叶子节点,将得到新的堆
算法性能分析
– 初始堆所需时间:O(n)
– 排序阶段:(不包含堆初始化)
– 重新构建堆所需时间,不超过O($\log_2 N$)
– n -1 次循环所需时间,不超过O(n $\log_2 N$)
– 时间复杂度:O(n $\log_2 N$ )
– 空间复杂度:O(1)
– 优点:堆排序在最坏情况下,无论是正序还是倒序,时间复杂度也为O(n $\log_2 N$ )
– 缺点:不稳定的排序,不适用于N比较小的场景