时间和空间复杂度

时间复杂度：

• 最好、平均和最坏情况： O(n log n)
  • 构建堆的时间复杂度为 O(n)，n 次提取操作中，每次筛选向下的时间复杂度为 O(log n)。不存在会导致性能下降的坏输入情况。

空间复杂度：

• O(1)
  • 堆排序会在原数组中重新排列元素，只需要常量级的额外内存。

总结：

• 堆排序兼具有保证的 O(n log n) 运行时间和 O(1) 额外空间，而归并排序和快速排序都无法同时做到这一点。
• 它不是稳定的（相等元素的相对顺序可能改变），这是它的主要取舍。