堆排序

(图片来自 堆排序 - 十大经典排序算法

思路

堆排序其实就是利用了「最大堆」的一个性质:父结点的值一定大于子结点,然后每次取最大堆的堆顶元素,即剩下的所有数中的最大值。其算法步骤如下:

  1. 将待排序序列转成最大堆(heapify)。
  2. 取堆顶元素出来,剩下的未排序序列再转成最大堆。如果只是单纯取值然后重新 heapify,成本较高;因此一般是将堆顶元素与该堆的最后一个元素交换,然后将其移出最大堆,然后再执行 heapify。
  3. 重复执行第 2 步,直到最大堆的大小为 1。

这里涉及到两个细节:

  1. 如何在序列中表示最大堆?
    • 父结点 $i$ 的左子结点的位置为 $2 i + 1$。
    • 父结点 $i$ 的右子结点的位置为 $2 i + 2$。
    • 子结点 $i$ 的父结点的位置为 $\operatorname{floor}(\frac{i - 1}{2})$。
  2. 如何执行 heapify?
    • 从最大堆的末尾往开头遍历,每次遍历一个结点,都将该结点的值跟它的所有子孙结点进行对比(可以通过递归),如果大于子结点则交换两者。
    • 注意既要跟左子结点比较,也要跟右子结点比较,父结点只需要跟两个子结点中的较大值交换即可(堆不要求左右子结点的大小关系)。

分析

  • 由于使用了最大堆,其平均、最好、最坏时间复杂度都为 $O(n \log n)$。
  • 空间复杂度为 $O(1)$,不需要额外空间。
  • 算法不稳定。

实现

见《🔢 排序算法 00. 代码实现》(本博客)。