堆排序 Heap Sort
选择排序 · 用二叉堆加速「选最值」
什么是堆排序
堆排序是选择排序的高效版。选择排序每轮要线性扫描才能找到最大值；堆排序先把数组组织成一个大顶堆（完全二叉树，每个父节点都 ≥ 子节点，堆顶即全局最大），此后每次「取最值」只需 O(log n)。它把整体复杂度从 O(n²) 拉到 O(n log n)，而且原地、不需要额外数组。
它怎么做
两个阶段：①建堆（Floyd 方法，从最后一个非叶节点往前逐个 siftDown 下沉）；②排序——反复把堆顶（最大值）和堆末交换、堆缩小 1、对新堆顶再 siftDown 恢复堆序。点「下一步」看 [7, 6, 5, 10, 9, 8, 4, 3, 2, 1]：数组按完全二叉树布局显示在树轨上，当前正在下沉的节点深紫高亮，堆顶不断被「摘」到右端就位变绿。
7
6
5
10
9
8
4
3
2
1
建堆：对节点 4 做 siftDown
复杂度与适用
时间 O(n log n)（建堆 O(n) + n 次 O(log n) 提取）、原地、不稳定。它的独特价值是最坏也保证 O(n log n) 且不吃额外内存——这正是 IntroSort 用它兜底、防快排最坏退化的原因。堆结构本身更常以优先队列的形式出现在 Dijkstra、任务调度、Top-K 等场景。
堆排 = 选择排序 + 二叉堆：都是「反复取最值放到末尾」，区别在「取最值」用 O(log n) 的堆代替 O(n) 的线性扫描。
关联：堆这个结构在数据结构 · 堆页有独立讲解（建堆 / 上浮下沉 / 优先队列）。
关联：堆这个结构在数据结构 · 堆页有独立讲解（建堆 / 上浮下沉 / 优先队列）。
想深入堆本身（而不只是拿它排序），可回看数据结构 · 堆；想看堆排如何给快排「保底」，见 IntroSort（排序线进阶篇）。