 排序原理与多语言实现)
Hello 算法之堆排序基于大顶堆的原地 O(n log n) 排序原理与多语言实现【免费下载链接】hello-algo《Hello 算法》动画图解、一键运行的数据结构与算法教程。支持简中、繁中、English、日本語提供 Python, Java, C, C, C#, JS, Go, Swift, Rust, Ruby, Kotlin, TS, Dart 等代码实现项目地址: https://gitcode.com/GitHub_Trending/he/hello-algo堆排序Heap Sort是《Hello 算法》排序章节中“基于堆数据结构的 O(n log n) 排序算法”。本篇以 堆排序 文档为主体完整梳理其算法流程建堆、交换首尾、堆化修复、循环 n-1 轮并结合仓库中 Python 实现 与 C 实现 的源码深入讲解sift_down()为什么必须引入堆长度参数 n、建堆阶段为何是 O(n) 而非 O(n log n)以及堆排序“时间 O(n log n)、空间 O(1)、非稳定”三大特性的成因。读完本篇你可以从零手写一个原地堆排序并准确解释它的复杂度与稳定性问题。从“小顶堆 辅助数组”到“大顶堆 原地交换”堆排序是一种基于堆数据结构实现的高效排序算法。最直观的思路分两步输入数组并建立小顶堆此时最小元素位于堆顶不断执行出堆操作依次记录出堆元素即可得到从小到大排序的序列。以上方法虽然可行但需要借助一个额外数组来保存弹出的元素比较浪费空间。因此实际实现中通常采用一种更加优雅的方式直接利用原数组建立大顶堆反复把堆顶最大值“挪”到数组末尾。这样既不需要额外数组也能保持原地排序。仓库中“堆”章节的 MaxHeap.pop() 出堆操作恰好揭示了这两者的关系出堆本身就是“交换根节点与最右叶节点 → 删除节点 → 从顶至底堆化”三步。堆排序只是把其中的“删除节点”这一步省掉了——用“收缩堆的有效长度”代替物理删除从而把弹出元素天然地落在原数组的末尾形成已排序后缀。文档中的提示也指出元素出堆操作本身就包含交换首尾与堆化两步只是多了一个弹出元素的步骤。算法流程设数组的长度为 n堆排序的完整流程如下输入数组并建立大顶堆。完成后最大元素位于堆顶将堆顶元素第一个元素与堆底元素最后一个元素交换。完成交换后堆的长度减 1已排序元素数量加 1从堆顶元素开始从顶到底执行堆化操作sift down。完成堆化后堆的性质得到修复循环执行第 2 步和第 3 步。循环 n - 1 轮后即可完成数组排序。整个过程可以概括为“建堆一次、收缩 n-1 次”。建堆完成后数组左半部分是未排序的堆右半部分是已排序区每轮循环把当前堆的最大值沉入已排序区边界再通过堆化把堆性质恢复。核心源码解析sift_down()带长度参数的从顶至底堆化在代码实现中堆排序复用了“堆”章节中相同的从顶至底堆化sift_down()函数。值得特别注意的是由于堆的长度会随着提取最大元素而减小因此需要给sift_down()添加一个长度参数 n用于指定堆的当前有效长度。这一点在 Python 实现 中体现得非常清晰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从源码结构看这里的关键有两处左右子节点索引按堆完全二叉树的数组表示计算左子节点2 * i 1、右子节点2 * i 2与 MaxHeap 中的left()、right()完全一致边界判断使用l n、r n而不是l len(nums)。若缺少 n 参数堆化会“越界”到已排序区破坏已排好的后缀排序结果直接错误。heap_sort()建堆与排序两个阶段Python 版 heap_sort() 全文只有两个循环逻辑非常紧凑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)逐行对应算法流程建堆阶段从最后一个非叶节点len(nums) // 2 - 1开始倒序遍历对每个节点执行从顶至底堆化。倒序遍历保证了堆化某节点时其子树已经是合法的子堆因此一次堆化即可修复整棵子树。叶节点没有子节点天然就是合法子堆无须堆化所以起点是“最后一个节点的父节点”排序阶段外层循环i从len(nums) - 1递减到1恰好 n - 1 轮。每轮先交换nums[0]与nums[i]把当前最大值放到已排序区边界再调用sift_down(nums, i, 0)注意这里传入的有效堆长度是i而非len(nums)——上一轮交换进来的nums[i]已经不属于堆循环结束时下标 0 处剩下最后一个元素与下标 1 处相邻数组即为升序。C 实现 与 Python 版逐语句对应siftDown()使用l n nums[l] nums[ma]的短路条件做边界保护heapSort()同样分为nums.size() / 2 - 1倒序建堆与 n - 1 轮“swap siftDown”两个阶段。仓库中 Java、C#、JavaScript、TypeScript、Go、Rust、Swift、Ruby、Kotlin、Dart 等各语言目录下均有同构的heap_sort文件可对照阅读。建堆为什么是 O(n)文档的复杂度结论是“建堆操作使用 O(n) 时间”这个结论并非显然——如果对 n 个元素逐个“入堆”每次 O(log n)建堆就是 O(n log n)。仓库中 建堆操作 一节给出了更严格的推导值得展开需要堆化的节点只有非叶节点数量为n / 2整除一个节点从顶至底堆化的最大迭代次数等于它到叶节点的距离即节点高度最大为树高log n朴素地把两者相乘会高估为 O(n log n)但这忽略了“底层节点数量远多于顶层节点”的性质。精确算法是假设一棵高度为 h 的完美二叉树对每一层“节点数量 × 节点高度”求和$$T(h) 2^0 h 2^1 (h-1) 2^2 (h-2) \dots 2^{(h-1)} \times 1$$用错位相减法将上式乘以 2 再相减化简可得 $T(h) 2^{h1} - h - 2 O(2^h)$而完美二叉树的节点数 $n 2^{h1} - 1$故 $T(h) O(n)$。结论输入列表并建堆的时间复杂度为 O(n)。这也解释了源码中建堆循环为什么能直接对原数组倒序遍历一次完成——叶节点天然合法、每层节点数按 2 的幂增长使得总堆化代价被 O(n) 主导。Python 标准库的heapq.heapify()同样利用了这一点heap.py 的注释明确写明“输入列表并建堆时间复杂度为 O(n)而非 O(nlogn)”。算法特性与复杂度分析结合源码结构文档给出的三大特性可以逐一落实时间复杂度为 O(n log n)、非自适应排序建堆 O(n)排序阶段每轮堆化的代价为 O(log n)堆化路径最长为树高共 n - 1 轮合计 O(n log n)。排序开销完全由堆的高度决定与输入元素的初始有序程度无关因此堆排序是非自适应排序——即使输入近乎有序也不会像插入排序那样退化加速空间复杂度为 O(1)、原地排序从源码看heap_sort()只使用了几个索引变量i、l、r、ma没有申请辅助数组元素交换和堆化全部在原数组上进行。这与“小顶堆 记录弹出元素”的初版思路相比正是“更加优雅的实现方式”省下的那部分空间非稳定排序稳定性要求相等元素的相对顺序在排序后保持不变。而堆排序每轮都把堆顶与堆底交换且堆化过程中元素会沿树向下跳跃交换两个相等元素完全可能因为处于不同分支而被交换先后因此相等元素的相对位置可能发生变化堆排序不是稳定排序。运行验证各语言示例均以相同的驱动代码验证正确性。以 heap_sort.py 为例Driver Code if __name__ __main__: nums [4, 1, 3, 1, 5, 2] heap_sort(nums) print(堆排序完成后 nums , nums)输入[4, 1, 3, 1, 5, 2]排序完成后输出堆排序完成后 nums [1, 1, 2, 3, 4, 5]。注意样例中特意包含两个相等的1可以直观地观察非稳定性排序后两个 1 的相对位置由交换过程决定并不保证与输入一致。C 版 heap_sort.cpp 使用同一组数据[4, 1, 3, 1, 5, 2]输出堆排序完成后 nums [1, 1, 2, 3, 4, 5]。小结堆排序是“堆”数据结构最典型的工程化应用其精髓在于三点原地化用“交换首尾 收缩有效长度”替代“弹出元素存入辅助数组”把 O(n) 额外空间压缩到 O(1)长度参数sift_down(nums, n, i)中的 n 是堆当前有效长度是正确性关键——边界判断l n、r n保证堆化永不越界到已排序区复杂度画像建堆 O(n)靠倒序遍历 层级加和的精确推导排序 O(n log n)空间 O(1)代价是非稳定、非自适应。与快速排序同为 O(n log n) 量级相比堆排序的优势在于最坏情况仍然 O(n log n)、空间 O(1)劣势则在于常数因子较大、缓存局部性较差且不稳定。这也是仓库中同时收录归并、快排、堆排等多种 O(n log n) 算法的意义实际选型需要结合稳定性、最坏性能与内存约束综合权衡。【免费下载链接】hello-algo《Hello 算法》动画图解、一键运行的数据结构与算法教程。支持简中、繁中、English、日本語提供 Python, Java, C, C, C#, JS, Go, Swift, Rust, Ruby, Kotlin, TS, Dart 等代码实现项目地址: https://gitcode.com/GitHub_Trending/he/hello-algo创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 Hello 算法之堆排序：基于大顶堆的原地 O(n log n) 排序原理与多语言实现
Hello 算法之堆排序基于大顶堆的原地 O(n log n) 排序原理与多语言实现【免费下载链接】hello-algo《Hello 算法》动画图解、一键运行的数据结构与算法教程。支持简中、繁中、English、日本語提供 Python, Java, C, C, C#, JS, Go, Swift, Rust, Ruby, Kotlin, TS, Dart 等代码实现项目地址: https://gitcode.com/GitHub_Trending/he/hello-algo堆排序Heap Sort是《Hello 算法》排序章节中“基于堆数据结构的 O(n log n) 排序算法”。本篇以 堆排序 文档为主体完整梳理其算法流程建堆、交换首尾、堆化修复、循环 n-1 轮并结合仓库中 Python 实现 与 C 实现 的源码深入讲解sift_down()为什么必须引入堆长度参数 n、建堆阶段为何是 O(n) 而非 O(n log n)以及堆排序“时间 O(n log n)、空间 O(1)、非稳定”三大特性的成因。读完本篇你可以从零手写一个原地堆排序并准确解释它的复杂度与稳定性问题。从“小顶堆 辅助数组”到“大顶堆 原地交换”堆排序是一种基于堆数据结构实现的高效排序算法。最直观的思路分两步输入数组并建立小顶堆此时最小元素位于堆顶不断执行出堆操作依次记录出堆元素即可得到从小到大排序的序列。以上方法虽然可行但需要借助一个额外数组来保存弹出的元素比较浪费空间。因此实际实现中通常采用一种更加优雅的方式直接利用原数组建立大顶堆反复把堆顶最大值“挪”到数组末尾。这样既不需要额外数组也能保持原地排序。仓库中“堆”章节的 MaxHeap.pop() 出堆操作恰好揭示了这两者的关系出堆本身就是“交换根节点与最右叶节点 → 删除节点 → 从顶至底堆化”三步。堆排序只是把其中的“删除节点”这一步省掉了——用“收缩堆的有效长度”代替物理删除从而把弹出元素天然地落在原数组的末尾形成已排序后缀。文档中的提示也指出元素出堆操作本身就包含交换首尾与堆化两步只是多了一个弹出元素的步骤。算法流程设数组的长度为 n堆排序的完整流程如下输入数组并建立大顶堆。完成后最大元素位于堆顶将堆顶元素第一个元素与堆底元素最后一个元素交换。完成交换后堆的长度减 1已排序元素数量加 1从堆顶元素开始从顶到底执行堆化操作sift down。完成堆化后堆的性质得到修复循环执行第 2 步和第 3 步。循环 n - 1 轮后即可完成数组排序。整个过程可以概括为“建堆一次、收缩 n-1 次”。建堆完成后数组左半部分是未排序的堆右半部分是已排序区每轮循环把当前堆的最大值沉入已排序区边界再通过堆化把堆性质恢复。核心源码解析sift_down()带长度参数的从顶至底堆化在代码实现中堆排序复用了“堆”章节中相同的从顶至底堆化sift_down()函数。值得特别注意的是由于堆的长度会随着提取最大元素而减小因此需要给sift_down()添加一个长度参数 n用于指定堆的当前有效长度。这一点在 Python 实现 中体现得非常清晰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从源码结构看这里的关键有两处左右子节点索引按堆完全二叉树的数组表示计算左子节点2 * i 1、右子节点2 * i 2与 MaxHeap 中的left()、right()完全一致边界判断使用l n、r n而不是l len(nums)。若缺少 n 参数堆化会“越界”到已排序区破坏已排好的后缀排序结果直接错误。heap_sort()建堆与排序两个阶段Python 版 heap_sort() 全文只有两个循环逻辑非常紧凑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)逐行对应算法流程建堆阶段从最后一个非叶节点len(nums) // 2 - 1开始倒序遍历对每个节点执行从顶至底堆化。倒序遍历保证了堆化某节点时其子树已经是合法的子堆因此一次堆化即可修复整棵子树。叶节点没有子节点天然就是合法子堆无须堆化所以起点是“最后一个节点的父节点”排序阶段外层循环i从len(nums) - 1递减到1恰好 n - 1 轮。每轮先交换nums[0]与nums[i]把当前最大值放到已排序区边界再调用sift_down(nums, i, 0)注意这里传入的有效堆长度是i而非len(nums)——上一轮交换进来的nums[i]已经不属于堆循环结束时下标 0 处剩下最后一个元素与下标 1 处相邻数组即为升序。C 实现 与 Python 版逐语句对应siftDown()使用l n nums[l] nums[ma]的短路条件做边界保护heapSort()同样分为nums.size() / 2 - 1倒序建堆与 n - 1 轮“swap siftDown”两个阶段。仓库中 Java、C#、JavaScript、TypeScript、Go、Rust、Swift、Ruby、Kotlin、Dart 等各语言目录下均有同构的heap_sort文件可对照阅读。建堆为什么是 O(n)文档的复杂度结论是“建堆操作使用 O(n) 时间”这个结论并非显然——如果对 n 个元素逐个“入堆”每次 O(log n)建堆就是 O(n log n)。仓库中 建堆操作 一节给出了更严格的推导值得展开需要堆化的节点只有非叶节点数量为n / 2整除一个节点从顶至底堆化的最大迭代次数等于它到叶节点的距离即节点高度最大为树高log n朴素地把两者相乘会高估为 O(n log n)但这忽略了“底层节点数量远多于顶层节点”的性质。精确算法是假设一棵高度为 h 的完美二叉树对每一层“节点数量 × 节点高度”求和$$T(h) 2^0 h 2^1 (h-1) 2^2 (h-2) \dots 2^{(h-1)} \times 1$$用错位相减法将上式乘以 2 再相减化简可得 $T(h) 2^{h1} - h - 2 O(2^h)$而完美二叉树的节点数 $n 2^{h1} - 1$故 $T(h) O(n)$。结论输入列表并建堆的时间复杂度为 O(n)。这也解释了源码中建堆循环为什么能直接对原数组倒序遍历一次完成——叶节点天然合法、每层节点数按 2 的幂增长使得总堆化代价被 O(n) 主导。Python 标准库的heapq.heapify()同样利用了这一点heap.py 的注释明确写明“输入列表并建堆时间复杂度为 O(n)而非 O(nlogn)”。算法特性与复杂度分析结合源码结构文档给出的三大特性可以逐一落实时间复杂度为 O(n log n)、非自适应排序建堆 O(n)排序阶段每轮堆化的代价为 O(log n)堆化路径最长为树高共 n - 1 轮合计 O(n log n)。排序开销完全由堆的高度决定与输入元素的初始有序程度无关因此堆排序是非自适应排序——即使输入近乎有序也不会像插入排序那样退化加速空间复杂度为 O(1)、原地排序从源码看heap_sort()只使用了几个索引变量i、l、r、ma没有申请辅助数组元素交换和堆化全部在原数组上进行。这与“小顶堆 记录弹出元素”的初版思路相比正是“更加优雅的实现方式”省下的那部分空间非稳定排序稳定性要求相等元素的相对顺序在排序后保持不变。而堆排序每轮都把堆顶与堆底交换且堆化过程中元素会沿树向下跳跃交换两个相等元素完全可能因为处于不同分支而被交换先后因此相等元素的相对位置可能发生变化堆排序不是稳定排序。运行验证各语言示例均以相同的驱动代码验证正确性。以 heap_sort.py 为例Driver Code if __name__ __main__: nums [4, 1, 3, 1, 5, 2] heap_sort(nums) print(堆排序完成后 nums , nums)输入[4, 1, 3, 1, 5, 2]排序完成后输出堆排序完成后 nums [1, 1, 2, 3, 4, 5]。注意样例中特意包含两个相等的1可以直观地观察非稳定性排序后两个 1 的相对位置由交换过程决定并不保证与输入一致。C 版 heap_sort.cpp 使用同一组数据[4, 1, 3, 1, 5, 2]输出堆排序完成后 nums [1, 1, 2, 3, 4, 5]。小结堆排序是“堆”数据结构最典型的工程化应用其精髓在于三点原地化用“交换首尾 收缩有效长度”替代“弹出元素存入辅助数组”把 O(n) 额外空间压缩到 O(1)长度参数sift_down(nums, n, i)中的 n 是堆当前有效长度是正确性关键——边界判断l n、r n保证堆化永不越界到已排序区复杂度画像建堆 O(n)靠倒序遍历 层级加和的精确推导排序 O(n log n)空间 O(1)代价是非稳定、非自适应。与快速排序同为 O(n log n) 量级相比堆排序的优势在于最坏情况仍然 O(n log n)、空间 O(1)劣势则在于常数因子较大、缓存局部性较差且不稳定。这也是仓库中同时收录归并、快排、堆排等多种 O(n log n) 算法的意义实际选型需要结合稳定性、最坏性能与内存约束综合权衡。【免费下载链接】hello-algo《Hello 算法》动画图解、一键运行的数据结构与算法教程。支持简中、繁中、English、日本語提供 Python, Java, C, C, C#, JS, Go, Swift, Rust, Ruby, Kotlin, TS, Dart 等代码实现项目地址: https://gitcode.com/GitHub_Trending/he/hello-algo创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考