堆排序的原理和过程是什么？它稳定吗？

简化版

堆排序分两步：① 建堆——把数组原地建成大顶堆（升序排序用大顶堆），O(n)；② 反复取最值——把堆顶（最大值）和末尾元素交换，堆大小减 1，再对新堆顶下沉恢复堆序；重复 n-1 次。每次都把当前最大值「甩」到数组末尾，最终得到升序。时间 O(n log n)、原地 O(1) 空间、不稳定。

详细版

void heapSort(int[] a) {
    int n = a.length;
    // 1. 建大顶堆（O(n)）
    for (int i = n/2 - 1; i >= 0; i--) siftDown(a, i, n);
    // 2. 反复把堆顶换到末尾，缩小堆并下沉
    for (int end = n - 1; end > 0; end--) {
        swap(a, 0, end);          // 当前最大值放到 end 位置（已排好）
        siftDown(a, 0, end);      // 对前 end 个元素重新下沉，堆缩小 1
    }
}

升序排序用大顶堆：每次取出的最大值放到末尾，从后往前排好。
降序排序用小顶堆：每次取最小值放末尾。
排序区间逐步缩小：end 从 n-1 递减，[0, end) 是剩余的堆、[end, n) 是已排好的部分。

完整版教学

一、堆排序的核心思想

堆排序本质是「选择排序的高效版」。选择排序每轮要 O(n) 地扫一遍找最大值，n 轮就是 O(n²)。堆排序用堆把「找最大值」从 O(n) 降到 O(log n)（取堆顶 + 下沉），于是总复杂度降到 O(n log n)。所以堆排序 = 用堆加速的选择排序。

二、为什么升序用大顶堆

这一点容易搞反。升序排序（从小到大）要用大顶堆：

大顶堆的堆顶是最大值。
每次把堆顶（最大值）和当前堆的最后一个位置交换——最大值就被放到了数组尾部它该在的位置。
然后堆缩小 1（末尾那个已排好，不再参与），对新堆顶下沉。
重复，最大值、次大值……依次填到数组尾部，从后往前排好，最终整体升序。

反过来，降序排序用小顶堆（每次把最小值甩到末尾）。记忆：升序用大顶堆、降序用小顶堆（和直觉相反，别记错）。

三、完整流程走一遍

数组 [3,1,2]，升序：
建大顶堆: [3,1,2]（已是大顶堆）
end=2: swap(0,2) → [2,1,3]，siftDown 前2个 → [2,1,3]
end=1: swap(0,1) → [1,2,3]，siftDown 前1个 → [1,2,3]
结果 [1,2,3] 升序 ✓

四、复杂度与特性

时间 O(n log n)：建堆 O(n) + n 次「取堆顶 + 下沉 O(log n)」= O(n log n)。最好、最坏、平均都是 O(n log n)，很稳定的性能（不会像快排最坏退化到 O(n²)）。
空间 O(1)：原地排序，只用常数额外空间（不像归并要 O(n) 辅助数组）。
不稳定：相等元素的相对顺序可能被打乱（交换堆顶到末尾、下沉时会跨越相等元素）。

五、堆排序 vs 快排 vs 归并

	堆排序	快速排序	归并排序
平均时间	O(n log n)	O(n log n)	O(n log n)
最坏时间	O(n log n)	O(n²)	O(n log n)
空间	O(1)	O(log n)	O(n)
稳定性	不稳定	不稳定	稳定

堆排序的优势是最坏也 O(n log n) 且原地 O(1) 空间。但实际中快排常更快（堆排序的跳跃式访问对缓存不友好，常数较大），所以「保证最坏性能 + 省空间」时选堆排序，追求平均速度选快排，要稳定选归并。

六、常见误区与追问

考点	正确口径
建堆	先把数组 heapify 成大顶堆
选择最大	堆顶和末尾交换
缩小堆	末尾确定，剩余部分下沉恢复堆

heapify(nums)
for end from n-1 downto 1:
  swap(0, end)
  heapSize--
  siftDown(0)

升序堆排序用大顶堆，因为每轮把当前最大值放到数组尾部。

误区：升序排序应该用小顶堆。 原地堆排序升序通常用大顶堆，把最大值不断放到右侧最终位置。
误区：堆排序是稳定排序。 堆中远距离交换会打乱相等元素的原始相对顺序，因此不稳定。
误区：建堆阶段是 O(n log n)。 Floyd 自底向上建堆是 O(n)，整体复杂度主要来自 n 次下沉，O(n log n)。
追问：堆排序空间复杂度是多少？ 原地堆排序额外空间 O(1)，这点优于归并排序常见实现。
追问：为什么实际常不如快排快？ 堆排序访问跳跃，缓存局部性较差；快排分区通常更 cache friendly。
追问：堆排序适合什么场景？ 需要 O(1) 额外空间且希望最坏 O(n log n) 时可以考虑。

七、加强记忆

堆排序两步：建大顶堆（O(n)）→ 反复「堆顶与末尾交换、堆缩小 1、新堆顶下沉」，把最大值依次甩到尾部，从后往前排好。升序用大顶堆、降序用小顶堆（别记反）。时间 O(n log n)（最坏也是）、空间 O(1)、不稳定。相比快排胜在「最坏 O(n log n) 且原地」，但缓存不友好、实际常比快排慢。

简化版

详细版