Hello 算法堆排序全解析：从建堆到原地 O(1) 空间完成排序

导读

堆排序（heap sort）是《Hello 算法》排序章节中基于堆数据结构的代表性排序算法，它复用了"堆"章节中已经掌握的建堆与元素出堆操作，实现原地、最坏情况时间复杂度 O(n log n) 的排序。本文将基于 ja/docs/chapter_sorting/heap_sort.md 的完整骨架，结合仓库内 14 种语言的源码实现与实测运行结果，讲解大顶堆原地升序排序的算法流程、带长度参数的 sift_down() 堆化细节、时空复杂度推导，并给出可直接复现运行的命令。

---

从朴素方案到优雅方案：为什么选大顶堆

堆排序的基本思路非常直观：堆顶天然承载着全局最大（大顶堆）或全局最小（小顶堆）元素，只要能反复取出堆顶，就能得到一个有序序列。

最朴素的实现方式如下：

1. 输入数组并建立小顶堆，此时最小元素位于堆顶；
2. 不断执行出堆操作，依次记录弹出的元素，即可得到从小到大排序的序列。

这种方案虽然在逻辑上无懈可击，但每次出堆都要把弹出的元素保存到一个额外的数组中，需要额外 O(n) 的空间，比较浪费。

因此实际实现中通常使用一种更优雅的方式：建立大顶堆，把最大元素交换到数组末尾，直接在原数组上完成排序：

1. 输入数组并建立大顶堆，此时最大元素位于堆顶（即数组第一个元素）；
2. 将堆顶元素（第一个元素）与堆底元素（最后一个元素）交换，使最大元素就位到数组末尾的有序区；
3. 堆的长度随之减 1，已排序元素数量加 1；
4. 循环执行交换与堆化，直到所有元素就位。

阅读本节前，请确保已经学完"堆"章节——堆排序直接依赖其中的建堆操作与 sift_down() 堆化操作，二者的实现细节可在 docs/chapter_heap/heap.md 与 docs/chapter_heap/build_heap.md 中复习。

算法流程：4 个步骤循环 n-1 轮

设数组长度为 n，大顶堆堆排序的完整流程如下：

1. 建堆：输入数组并建立大顶堆。完成后，最大元素位于堆顶；
2. 交换：将堆顶元素（第一个元素）与堆底元素（最后一个元素）交换。交换完成后，堆的长度减 1，已排序元素数量加 1——数组末尾多出的那个位置不再属于堆；
3. 堆化：从新的堆顶元素开始，自顶向下执行堆化操作（sift down），修复因交换而破坏的堆性质；
4. 循环：重复执行第 2、3 步。循环 n - 1 轮后，堆中只剩 1 个元素（它必然是最小元素），此时整个数组完成升序排序。

一个值得注意的对应关系：上一章学习的"元素出堆操作"本质上就包含第 2、3 步——取出堆顶前先把堆顶与堆底交换、缩短堆长度，再对新的堆顶做一次自顶向下堆化；堆排序只是省去了"弹出元素"这个步骤，让被交换到末尾的最大元素直接留在原地充当已排序区。

下图三张步骤图依次展示了大顶堆建堆后的初态、交换与堆化的中间过程，以及排序完成的终态（分步图素材位于 heap_sort.assets 目录，共 12 张）。

源码实现：带长度参数的 sift_down()

堆排序与"堆"章节代码的最大差异在于：堆的有效长度会随着每次取出最大元素而不断减小。因此，代码中复用的自顶向下堆化函数必须额外增加一个长度参数 n，用来指定堆当前的边界，防止堆化时越过已排序区域、把已经归位的元素重新拉回堆中。

下面是 Python 版完整实现，逻辑与仓库内所有语言版本一一对应（见 codes/python/chapter_sorting/heap_sort.py）：

def sift_down(nums: list[int], n: int, i: int):
    """堆的长度为 n ，从节点 i 开始，从顶至底堆化"""
    while True:
        # 判断节点 i, l, r 中值最大的节点，记为 ma
        l = 2 * i + 1
        r = 2 * i + 2
        ma = i
        if l < n and nums[l] > nums[ma]:
            ma = l
        if r < n and nums[r] > nums[ma]:
            ma = r
        # 若节点 i 最大或索引 l, r 越界，则无须继续堆化，跳出
        if ma == i:
            break
        # 交换两节点
        nums[i], nums[ma] = nums[ma], nums[i]
        # 循环向下堆化
        i = ma


def heap_sort(nums: list[int]):
    """堆排序"""
    # 建堆操作：堆化除叶节点以外的其他所有节点
    for i in range(len(nums) // 2 - 1, -1, -1):
        sift_down(nums, len(nums), i)
    # 从堆中提取最大元素，循环 n-1 轮
    for i in range(len(nums) - 1, 0, -1):
        # 交换根节点与最右叶节点（交换首元素与尾元素）
        nums[0], nums[i] = nums[i], nums[0]
        # 以根节点为起点，从顶至底进行堆化
        sift_down(nums, i, 0)

关键实现细节拆解

• 子节点下标公式：以数组下标 0 为根，节点 i 的左子节点为 2 * i + 1，右子节点为 2 * i + 2（见 C 版 heap_sort.c 中的 siftDown）；
• 堆化终止条件：在 i、l、r 三者中找出值最大的下标 ma；若 ma == i（节点 i 已大于两个子节点）或 l、r 越界，则跳出；否则交换 nums[i] 与 nums[ma]，并令 i = ma 继续向下迭代；
• 建堆起点 n // 2 - 1：这是最后一个非叶节点的下标。叶节点本身已是单节点堆，无需堆化；从最后一个非叶节点开始自底向上逐个堆化，即可在 O(n) 时间内完成整个建堆过程（见 docs/chapter_heap/build_heap.md 中关于第二类建堆方法时间复杂度为 O(n) 的等比数列推导）；
• 每轮堆长度递减：提取阶段的循环变量 i 同时充当"当前堆长度"——交换 nums[0] 与 nums[i] 后，对前 i 个元素（即缩短后的堆）从根节点重新堆化，尾部的已排序区永远不被触碰。

多语言对照与运行验证

同样的函数在仓库中提供了 14 种实现，逻辑完全一致：C（heap_sort.c）、C++（heap_sort.cpp）、C#（heap_sort.cs）、Dart、Go、Java、JavaScript、Kotlin、Python、Ruby、Rust、Swift、TypeScript 以及 PythonTutor 分步演示（heap_sort.md）；日文代码目录 ja/codes 同样提供完整副本。

以仓库内置的示例数组 [4, 1, 3, 1, 5, 2] 实测运行：

python3 codes/python/chapter_sorting/heap_sort.py

输出为：

堆排序完成后 nums = [1, 1, 2, 3, 4, 5]

可以手动推演其中一轮：建堆完成后堆顶为最大值 5；将其与堆底 2 交换后，2 位于堆顶，对前 5 个元素 [2, 4, 3, 1, 1] 自顶向下堆化，重新让 4 浮到堆顶……如此往复，最大值依次归位到数组尾部，最终得到升序序列。

算法特性：复杂度与稳定性

堆排序的三项核心特性可总结如下表：

指标	结论	依据
时间复杂度	O(n log n)，非自适应	建堆 O(n) + n-1 轮 × 每轮堆化 O(log n)
空间复杂度	O(1)，原地排序	仅使用若干指针/索引变量，交换与堆化都在原数组上进行
稳定性	非稳定排序	交换堆顶与堆底元素时，相等元素的相对位置可能发生改变

展开说明如下：

• 非自适应排序：无论输入数据是几乎有序还是完全逆序，建堆都要遍历全部非叶节点，提取阶段也固定循环 n - 1 轮、每轮堆化与堆高 log n 相关，因此最好、平均、最坏时间复杂度恒为 O(n log n)，性能不随数据分布而波动。这一点优于快速排序（最坏退化为 O(n²)），但常数因子通常大于快排与归并排序；
• 建堆为何是 O(n) 而非 O(n log n)：若逐个将元素插入堆，每个元素需 O(log n)，总代价为 O(n log n)；但自底向上对每个非叶节点执行一次堆化，多数节点堆高很低、下潜距离短，总工作量是一个可求和收敛的等比数列，最终为 O(n)。完整推导见 docs/chapter_heap/build_heap.md；
• 原地 O(1) 空间：整个排序过程不申请与 n 相关的辅助结构，仅靠交换数组内部元素完成，这让堆排序在内存受限场景（如嵌入式环境）中极具吸引力；
• 非稳定性的来源：大顶堆不保证相等元素的相对次序。在建堆阶段的父子交换、以及提取阶段"堆顶↔堆底"的大跨度交换中，相等的元素可能被越过或对调。例如数组 [1a, 1b] 中两个相等的 1，经建堆与交换后，1a、1b 的先后次序并不保证与输入一致。若业务要求稳定的排序结果，应改用归并排序或插入排序等稳定算法。

与其他排序的横向对照

将堆排序放进《Hello 算法》排序章节的整体坐标系中，可以更清楚地把握其定位：

• 与选择排序的关系：堆排序可以看作选择排序的堆优化版——选择排序每轮线性扫描找最小（大）值，耗时 O(n)，堆排序则利用堆结构把"找极值"降为 O(log n)，从而把整体复杂度从 O(n²) 提升到 O(n log n)；
• 与归并排序的关系：堆排序与归并排序同为 O(n log n)，但归并排序需要 O(n) 辅助空间（或复杂链表技巧），堆排序却能做到严格原地 O(1)；
• 与快速排序的关系：堆排序没有快排"最坏退化为 O(n²)"的隐患，最坏情况依然是 O(n log n)，适合对最坏时延敏感、又不允许 O(n) 辅助空间的场合；
• 稳定性取舍：上述 O(n log n) 比较类排序中，归并排序可做到稳定，快排与堆排序均为非稳定，需要稳定排序时应另行选择算法。

各排序的详细对比与适用场景，可继续阅读 docs/chapter_sorting/sorting_algorithm.md 与 docs/chapter_sorting/summary.md；堆数据结构的建堆与出入堆基础，可回看 docs/chapter_heap/heap.md、docs/chapter_heap/build_heap.md。

小结

堆排序是对"堆"这一数据结构最典型的工程化应用：它先利用自底向上的堆化在 O(n) 时间内把无序数组整理成一个大顶堆，再通过 n - 1 轮"交换堆顶与堆底 + 缩短堆长度 + 自顶向下堆化" 让最大值逐个就位于数组尾部，最终在原地、O(1) 辅助空间内以最坏 O(n log n) 的稳定耗时完成升序排序。读懂堆排序的关键，是理解为什么堆化函数必须携带长度参数 n，以及"大顶堆 + 交换"如何将朴素小顶堆方案中那块浪费的额外数组彻底消除。