堆排序 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
1function heapSort(a: number[]): number[] {
2 const n = a.length;
3 for (let i = Math.floor(n / 2) - 1; i >= 0; i--)
4 siftDown(a, i, n);
5 for (let end = n - 1; end > 0; end--) {
6 [a[0], a[end]] = [a[end], a[0]];
7 siftDown(a, 0, end);
8 }
9 return a;
10}
11function siftDown(a: number[], i: number, size: number) {
12 while (2 * i + 1 < size) {
13 let largest = i;
14 const l = 2 * i + 1, r = 2 * i + 2;
15 if (a[l] > a[largest]) largest = l;
16 if (r < size && a[r] > a[largest]) largest = r;
17 if (largest === i) break;
18 [a[i], a[largest]] = [a[largest], a[i]];
19 i = largest;
20 }
21}
n10
阶段建堆
heapSize10
i4
left9
right-
largest4
swapCount0
1 / 57
复杂度与适用
时间 O(n log n)（建堆 O(n) + n 次 O(log n) 提取）、原地、不稳定。它的独特价值是最坏也保证 O(n log n) 且不吃额外内存——这正是 IntroSort 用它兜底、防快排最坏退化的原因。堆结构本身更常以优先队列的形式出现在 Dijkstra、任务调度、Top-K 等场景。
堆排 = 选择排序 + 二叉堆：都是「反复取最值放到末尾」，区别在「取最值」用 O(log n) 的堆代替 O(n) 的线性扫描。
关联：堆这个结构在数据结构 · 堆页有独立讲解（建堆 / 上浮下沉 / 优先队列）。
关联：堆这个结构在数据结构 · 堆页有独立讲解（建堆 / 上浮下沉 / 优先队列）。
想深入堆本身（而不只是拿它排序），可回看数据结构 · 堆；想看堆排如何给快排「保底」，见 IntroSort（排序线进阶篇）。