文档目录

一、核心思路：利用二叉堆

堆排序分两步：

  1. 建堆：把数组变成最大堆（父节点 ≥ 子节点）。
  2. 排序：反复把堆顶（最大值）交换到数组末尾，然后调整剩余部分为堆。

heapify 整体操作流程：

  1. 初始化：假设当前节点 i 是最大值，记录其左右子节点位置。
  2. 找最大：比较 nums[i] 与其左右子节点，将最大值的索引赋值给 largest。
  3. 交换与下沉：如果 largest != i，交换 nums[i] 和 nums[largest]，然后递归对 largest 位置进行 heapify（下沉调整）。

heapSort 整体操作流程：

  1. 建堆：从最后一个非叶子节点（n/2 - 1）开始，从下往上调用 heapify，构建最大堆。
  2. 排序：循环 n-1 次：将堆顶（最大值）与末尾元素交换 → 堆大小减 1 → 对堆顶执行 heapify 恢复堆性质。
  3. 结果：所有元素交换完毕后，数组按升序排列。
void heapify(vector<int>& nums, int n, int i) {
    int largest = i;                               // ① 假设当前节点最大
    int left = 2 * i + 1;                          // ② 左子节点
    int right = 2 * i + 2;                         // ③ 右子节点

    if (left < n && nums[left] > nums[largest])    // ④ 左子更大 → 更新
        largest = left;
    if (right < n && nums[right] > nums[largest])  // ⑤ 右子更大 → 更新
        largest = right;

    if (largest != i) {                            // ⑥ 最大值不是当前节点
        swap(nums[i], nums[largest]);              // ⑦ 交换，让最大值上浮
        heapify(nums, n, largest);                 // ⑧ 递归下沉被换下去的节点
    }
}

void heapSort(vector<int>& nums) {
    int n = nums.size();

    for (int i = n / 2 - 1; i >= 0; i--) {         // ① 从最后一个非叶子节点开始建堆
        heapify(nums, n, i);
    }

    for (int i = n - 1; i > 0; i--) {              // ② 逐个取出堆顶
        swap(nums[0], nums[i]);                    // ③ 堆顶（最大值）放到末尾
        heapify(nums, i, 0);                       // ④ 对剩余 i 个元素调整堆
    }
}

建堆的过程（nums = [3, 7, 8, 5, 2, 1, 9]）：

初始数组：  3  7  8  5  2  1  9
树形：
      3
    /   \
   7     8
  / \   / \
 5   2 1   9

i=2 (值8)：8≥1,8≥9 → 和 9 交换
      3
    /   \
   7     9
  / \   / \
 5   2 1   8

i=1 (值7)：7≥5,7≥2 → 不动

i=0 (值3)：3≥7? → 和 7 交换
      7
    /   \
   3     9
  / \   / \
 5   2 1   8
3≥5 → 和 5 交换

      7
    /   \
   5     9
  / \   / \
 3   2 1   8

建堆完成！堆顶 9 是最大值。

二、堆排序的特性

时间复杂度：$O(N \log N)$（建堆 $O(N)$ + 排序 $O(N \log N)$） 空间复杂度：$O(1)$（原地排序） 稳定性：不稳定（堆顶和末尾元素交换时，可能破坏相等元素的相对顺序）

三、面试追问 Q&A

Q1：为什么建堆的时间复杂度是 $O(N)$ 而不是 $O(N \log N)$？ A：因为从下往上建堆，大部分节点高度小。高度为 0（叶子节点，占 N/2）不需要 heapify，高度为 1（N/4 个节点）最多下沉 1 层……总操作次数 = $\sum_{h=0}^{\log N} \frac{N}{2^{h+1}} \cdot h \approx N$。

Q2：堆排序比快排慢的原因？ A：快排对连续内存的顺序扫描对 CPU 缓存友好。堆排序的 heapify 是跳跃式访问（i → 2i+1 → 4i+2），每次访问的地址不连续，缓存命中率差。数据量越大差距越明显。