堆排序的时间复杂度为 O(n log n)，这一结论可以从其两个主要阶段进行分析：

一、堆排序的两个阶段

阶段 1：建堆（Build Heap）

• 将一个无序数组构建成一个最大堆（或最小堆）。
• 使用自底向上的 heapify 操作，从最后一个非叶子节点开始向上调整。

✅ 时间复杂度：O(n)
虽然每个 heapify 最坏是 O(log n)，但并不是所有节点都需要下沉 log n 层。
越靠近叶子的节点越多，但它们的下沉深度越小；越靠近根的节点越少，但下沉深。
通过数学求和可严格证明：
T(n) = sum_{h=0}^{log n} left( text{第 } h text{ 层节点数} times text{最大下沉深度} right)
= sum_{h=1}^{log n} 2^{log n - h} cdot h = O(n)
因此，建堆是线性时间 O(n)。

阶段 2：排序（Repeated Extraction）

• 执行 n−1 次 操作：
  1. 将堆顶（最大值）与末尾元素交换；
  2. 对剩余的 i 个元素（i 从 n−1 到 1）调用 heapify 重建堆。

每次 heapify 的时间复杂度为 O(log i)，因为堆高度为 ⌊log₂i⌋。

所以总时间为：

sum_{i=1}^{n-1} O(log i) = O(log 1 + log 2 + cdots + log (n-1)) = O(log((n-1)!))

利用斯特林公式（Stirling’s approximation）：

log(n!) = Theta(n log n)

因此：

sum_{i=1}^{n-1} log i = Theta(n log n)

✅ 排序阶段时间复杂度：O(n log n)

二、总时间复杂度

• 建堆：O(n)
• 排序：O(n log n)
• 总计：O(n) + O(n log n) = O(n log n)

三、为什么最好/最坏/平均都是 O(n log n)？

堆排序不依赖输入数据的初始顺序：

• 无论数组是否已排序、逆序或随机，建堆和每次 heapify 的操作次数基本不变。
• 因此：
  • 最好情况：Ω(n log n)
  • 最坏情况：O(n log n)
  • 平均情况：Θ(n log n)

📌 这一点与快速排序不同（快排最好 O(n log n)，最坏 O(n²)）。

事实上，有理论证明：堆排序的比较次数下界就是 Ω(n log n)，即使在最好情况下也无法更快（见你提供的博客中的精简证明）。

四、总结
阶段 操作 时间复杂度
建堆 自底向上 heapify O(n)
排序 n−1 次 heapify O(n log n)
总计 O(n log n)

✅ 所以，堆排序的时间复杂度稳定为 O(n log n)，适用于对性能要求稳定、且内存受限（原地排序）的场景。

如需图解或数学推导细节，也可以继续问我！