堆排序算法原理+手写C#完整源码

前言掌握堆排序Heap Sort是C#算法面试、数据结构笔试以及后端性能优化的关键也是LeetCode刷题中的高频难点。许多开发者仅停留在背诵时间复杂度的层面却难以理解堆调整逻辑、无法手写原生代码甚至混淆算法的稳定性与适用场景。本文采用纯原生C#实现零第三方依赖系统讲解堆排序的演变历程、核心概念、实现原理、完整流程和性能特点并提供可直接复用的源码实现。通过深入分析算法优缺点和适用场景确保读者从零基础到完全掌握轻松应对学习、面试、毕业设计和项目实战需求。全文内容紧凑实用建议收藏备用摘要堆排序是一种基于完全二叉树和大/小顶堆数据结构的原地选择排序算法。该算法由J. W. J. Williams在1964年首次提出后经Robert W. Floyd优化建堆过程现已成为计算机科学领域经典的十大排序算法之一。其核心流程包括构建堆、迭代交换堆顶元素和调整堆结构最终实现全局排序。堆排序的时间复杂度稳定最优、最坏和平均情况均为空间复杂度为属于原地且不稳定的排序算法。与其他排序算法相比堆排序具有显著优势避免了快速排序在最坏情况下的时间复杂度缺陷同时克服了归并排序需要额外空间的不足。这种兼顾时间稳定性和空间效率的特性使其在海量数据排序、TopK问题求解以及任务优先级调度等场景中得到广泛应用。本文将基于C#语言从零开始完整实现堆排序算法并深入解析每个步骤的执行逻辑及其背后的算法原理。基本概念堆的定义堆Heap是一种特殊的完全二叉树结构在计算机科学中具有广泛应用如优先队列、堆排序等。完全二叉树的定义是除最后一层外其余各层节点数均达到最大值完全填满且最后一层的节点从左至右连续排列。堆通常采用数组顺序存储这种实现方式无需指针结构能充分利用数组的连续内存特性使随机访问和顺序访问效率极高时间复杂度O(1)。这也是堆排序能够原地执行空间复杂度O(1)的关键所在。根据节点间的数值关系堆主要分为两种类型大顶堆最大堆任意父节点的值大于或等于其子节点的值。此结构保证堆顶元素始终为最大值。应用示例任务调度系统中优先级最高的任务总是位于堆顶。小顶堆最小堆任意父节点的值小于或等于其子节点的值。此结构保证堆顶元素始终为最小值。应用示例Dijkstra算法中用于快速获取当前最短路径。数组存储完全二叉树的核心公式堆排序算法通过数组下标隐式映射完全二叉树的节点关系这是实现堆排序的核心依据注意数组下标从0开始的情况节点关系计算公式已知父节点下标i左子节点下标 2*i 1右子节点下标 2*i 2已知子节点下标i父节点下标 floor((i - 1) / 2)向下取整最后一个非叶子节点下标arr.Length / 2 - 1例如长度为10的数组该值为4实际应用示例假设数组为[16,14,10,8,7,9,3,2,4,1]则元素16i0的左子节点是14i1右子节点是10i2元素7i4的父节点是14i1最后一个非叶子节点是7i4堆排序定义堆排序算法基于大/小顶堆的有序性通过以下步骤实现排序将待排序序列构建成一个大顶堆升序排序时将堆顶元素当前最大值与末尾元素交换缩小堆范围排除已排序的末尾元素调整剩余元素使其重新满足堆性质重复步骤2-4直到堆中只剩一个元素时间复杂度分析建堆过程O(n)每次堆调整O(logn)总体时间复杂度O(nlogn)典型应用场景需要部分排序的场景如Top K问题内存受限时的排序需求因为是原地排序需要稳定O(nlogn)时间复杂度的排序场景历史背景堆排序算法诞生于1964年是计算机算法发展史上的重要里程碑。其出现源于当时迫切的技术需求20世纪60年代初计算机应用迅速扩展数据处理需求激增但主流排序算法存在明显性能瓶颈传统算法局限冒泡排序、插入排序等简单算法虽然实现容易但的时间复杂度导致处理大规模数据时效率骤降。例如数据量从1000增至10000时排序时间可能增加100倍这在当时有限的计算资源下难以承受。快速排序问题1959年发明的快速排序平均时间复杂度为但对已排序或逆序数据等最坏情况下会退化至稳定性不足。归并排序缺陷1945年提出的归并排序虽具有稳定的时间复杂度但需要额外内存空间在早期内存资源极其稀缺的情况下代价过高。1964年成为关键转折点。英国计算机科学家J. W. J. Williams在《Communications of the ACM》发表了开创性论文《Algorithm 232: Heapsort》首次系统提出堆数据结构及配套排序算法。该算法的创新在于将数据视为完全二叉树结构通过堆化操作建立最大/最小堆性质利用堆顶元素特性实现高效排序这一突破同时解决了三个核心问题保持稳定的时间复杂度、仅需常数级额外空间、避免最坏情况性能退化。同年Robert W. Floyd进一步优化建堆过程提出自底向上调整的Floyd建堆算法将建堆时间复杂度从优化至显著提升了堆排序的整体性能。至此堆排序形成了标准范式使用Floyd算法将无序数组构建为堆反复取出堆顶元素与末尾元素交换对剩余元素重新堆化重复直至排序完成在后来的发展中堆排序因其独特优势得到广泛应用1970年代被纳入《计算机程序设计艺术》等经典著作1980年代成为计算机专业必修的核心内容现代编程语言如Java的Collections.sort、Python的sorted采用混合排序策略默认使用快速排序当递归深度过大可能触发最坏情况时自动切换为堆排序作为后备方案确保时间复杂度始终为堆排序的发明不仅解决了具体算法问题更开创了堆这一重要数据结构为优先队列、图算法等领域的发展奠定理论基础其影响延续至今。堆排序原理核心概念堆排序是选择排序的优化版本。传统选择排序每次遍历整个数组寻找极值时间复杂度较高每次选择极值为O(n)整体O(n²)。堆排序通过维护堆结构将查找极值的时间复杂度优化至O(log n)最终整体复杂度降至O(n log n)在处理大数据量时优势显著。算法流程堆排序包含两大核心操作和三个关键步骤核心操作堆调整HeapAdjust/Sift Down这是堆排序的核心函数其工作原理比较节点i与其左右子节点2i1和2i2若子节点值更大则与较大子节点交换递归调整交换后的位置直到节点大于等于子节点或到达叶节点假设节点i的子树已满足大顶堆性质通过这种下沉操作可使整棵子树恢复堆结构。由于堆是完全二叉树树高为log n单次调整时间复杂度为O(log n)。示例大顶堆调整 初始堆[16,14,10,8,7,9,3,2,4,1] 调整节点2值10比较子节点9和3选择9交换交换后[16,14,9,8,7,10,3,2,4,1]继续调整节点5原值10位置无子节点调整结束初始化建堆BuildHeap采用Floyd算法的自底向上建堆方法从最后一个非叶节点索引n/2-1开始向前遍历对每个节点执行堆调整将无序数组转换为大顶堆时间复杂度分析底层n/2叶节点无需调整倒数第二层n/4节点最多调整1次...根节点最多调整log n次 整体时间复杂度为O(n)这是堆排序高效的关键。排序过程建堆阶段 将无序数组构建为大顶堆此时堆顶元素arr[0]为最大值。 示例输入[3,1,4,1,5,9,2,6] → 建堆后[9,6,4,1,5,1,2,3]交换阶段 将堆顶最大值与堆尾元素交换完成一个元素的排序。 示例交换9和3 → [3,6,4,1,5,1,2,9]调整阶段 堆长度减1对新堆顶执行堆调整。 示例调整[3,6,4,1,5,1,2] → [6,5,4,1,3,1,2]迭代过程 重复交换、调整操作直到堆长度为0。 完整示例9落地 → [3,6,4,1,5,1,2,9]6落地 → [2,5,4,1,3,1,6,9]5落地 → [1,3,4,1,2,5,6,9] ... 最终结果[1,1,2,3,4,5,6,9]堆排序通过这种方式实现了O(n log n)的时间复杂度和O(1)的空间复杂度特别适合大数据量且内存受限的场景。执行流程以无序数组 [4, 6, 8, 5, 9] 为例完整拆解大顶堆升序排序过程初始化建堆建堆原理大顶堆是完全二叉树每个节点值 ≥ 子节点值非叶子节点范围数组长度n时最后一个非叶子节点下标为 ⌊n/2⌋-1调整方法从最后一个非叶子节点开始向前遍历对每个节点执行下沉操作具体步骤数组长度5 初始数组[4, 6, 8, 5, 9]索引对应0(4), 1(6), 2(8), 3(5), 4(9)确定调整起点最后一个非叶子节点⌊5/2⌋-1 1元素6调整顺序下标1 → 下标0调整下标1元素6左子节点2×113元素5右子节点2×124元素9比较6 5 但 6 9 → 交换6和9交换后数组[4, 9, 8, 5, 6]调整下标0元素4左子节点1元素9右子节点2元素8比较4 9 → 交换4和9下沉检查新位置1的元素4 vs 子节点5和6需要交换4和6最终数组[9, 6, 8, 5, 4]迭代排序排序原理将堆顶元素最大值与当前堆末尾元素交换堆大小减1对新堆顶元素执行下沉操作重复执行直到堆大小为1具体步骤第一轮排序当前堆[9, 6, 8, 5, 4]交换堆顶9与末尾4 → [4, 6, 8, 5, 9]有序部分[9]调整堆顶4比较子节点6、8 → 交换4和8新位置2的元素4 vs 子节点5 → 无需交换新堆[8, 6, 4, 5 | 9]第二轮排序交换堆顶8与末尾5 → [5, 6, 4, 8, 9]有序部分[8, 9]调整堆顶5比较子节点6、4 → 交换5和6新位置1的元素5 vs 无子节点 → 停止新堆[6, 5, 4 | 8, 9]第三轮排序交换堆顶6与末尾4 → [4, 5, 6, 8, 9]有序部分[6, 8, 9]调整堆顶4比较子节点5 → 交换4和5新位置1的元素4 vs 无子节点 → 停止新堆[5, 4 | 6, 8, 9]第四轮排序交换堆顶5与末尾4 → [4, 5, 6, 8, 9]有序部分[5, 6, 8, 9]堆大小1 → 排序完成最终结果[4, 5, 6, 8, 9] 升序排列可视化过程初始数组 [4, 6, 8, 5, 9] 建堆后 [9, 6, 8, 5, 4] 第一次交换后 [4, 6, 8, 5 | 9] 调整后堆 [8, 6, 4, 5 | 9] 第二次交换后 [5, 6, 4 | 8, 9] 调整后堆 [6, 5, 4 | 8, 9] 第三次交换后 [4, 5 | 6, 8, 9] 调整后堆 [5, 4 | 6, 8, 9] 第四次交换后 [4 | 5, 6, 8, 9] 最终结果 [4, 5, 6, 8, 9]算法性能分析时间复杂度初始化建堆堆化操作采用Floyd优化算法通过自底向上的堆化策略从最后一个非叶子节点索引n/2-1开始逐层向上调整时间复杂度推导叶子节点约n/2个无需调整倒数第二层约n/4个最多调整1次倒数第三层约n/8个最多调整2次...顶层根节点1个最多调整log n次总时间Σ (n/2^{k1}) * k ≈ O(n)优势相比逐个插入建堆的O(n log n)效率显著提升迭代堆调整操作流程交换堆顶元素与当前堆尾元素堆大小减1对新堆顶元素执行下沉操作(heapify)性能分析单次调整最坏情况O(log k)k为当前堆大小总调整次数n-1次数学推导综合复杂度对比场景快速排序归并排序堆排序最好情况O(n log n)O(n log n)O(n log n)最坏情况O(n²)O(n log n)O(n log n)平均情况O(n log n)O(n log n)O(n log n)工程应用适用于对最坏时间复杂度要求严格的实时系统如医疗设备、航天控制系统空间复杂度内存使用特性原地排序优势仅需3个额外存储单元元素交换的temp变量当前遍历索引i堆调整时的父子节点索引对比递归实现的快速排序最坏O(n)栈空间应用场景内存受限的嵌入式系统处理GB级大数据时快速排序递归实现using System; using System.Linq; public class QuickSort { public static int[] Sort(int[] arr) { if (arr.Length 1) return arr; int pivot arr[0]; var left arr.Skip(1).Where(x x pivot).ToArray(); var right arr.Skip(1).Where(x x pivot).ToArray(); return Sort(left).Concat(new[] { pivot }).Concat(Sort(right)).ToArray(); } }堆排序实现using System; public class HeapSort { public static void Sort(int[] arr) { int n arr.Length; for (int i n / 2 - 1; i 0; i--) Heapify(arr, n, i); for (int i n - 1; i 0; i--) { int temp arr[0]; arr[0] arr[i]; arr[i] temp; Heapify(arr, i, 0); } } private static void Heapify(int[] arr, int n, int i) { int largest i; int left 2 * i 1; int right 2 * i 2; if (left n arr[left] arr[largest]) largest left; if (right n arr[right] arr[largest]) largest right; if (largest ! i) { int swap arr[i]; arr[i] arr[largest]; arr[largest] swap; Heapify(arr, n, largest); } } }算法稳定性不稳定性表现根本原因堆顶与末尾元素的跨距离交换示例初始数组[5a, 3, 5b, 2] # 5a和5b为相等元素 建堆后[5a, 3, 5b, 2] 第一次交换[2, 3, 5b, 5a] # 5a被交换到最后 堆调整后[5b, 3, 2, 5a] # 5b上升到堆顶 最终结果[2, 3, 5b, 5a] # 原始顺序反转稳定性对比排序算法稳定性关键影响因素冒泡排序稳定相邻元素比较交换插入排序稳定元素逐个前移归并排序稳定合并时保持相等元素顺序快速排序不稳定分区时的元素跳跃交换堆排序不稳定堆顶与末尾元素的远程交换选择排序不稳定最小值与当前位置直接交换工程选择需要保持相等元素原始顺序时如数据库多字段排序优先选择稳定算法仅关注排序结果且内存受限时可接受堆排序的不稳定性完整可运行代码代码功能实现大顶堆升序排序实现小顶堆降序排序包含堆调整核心逻辑提供完整测试用例支持控制台输出验证兼容性适配.NET Framework、.NET Core及.NET 5全系列版本可直接复制运行。using System; namespace HeapSortDemo { /// summary /// 纯原生C#堆排序算法无任何第三方库 /// 包含大顶堆升序、小顶堆降序完整实现 /// public static class HeapSort { /// summary /// 大顶堆调整升序排序核心 /// /// param namearr待调整数组/param /// param nameparentIndex当前父节点下标/param /// param nameheapLength当前堆有效长度/param private static void MaxHeapAdjust(int[] arr, int parentIndex, int heapLength) { // 保存父节点值用于最终赋值 int temp arr[parentIndex]; // 左子节点下标 int leftChild 2 * parentIndex 1; // 循环下沉调整保证子树符合大顶堆规则 while (leftChild heapLength) { // 选取左右子节点中的最大值下标 int rightChild leftChild 1; int maxChildIndex leftChild; if (rightChild heapLength arr[rightChild] arr[leftChild]) { maxChildIndex rightChild; } // 父节点大于等于最大子节点无需调整直接退出 if (temp arr[maxChildIndex]) { break; } // 子节点值覆盖父节点 arr[parentIndex] arr[maxChildIndex]; // 更新下标继续下沉 parentIndex maxChildIndex; leftChild 2 * parentIndex 1; } // 将初始父节点值放入最终下沉位置 arr[parentIndex] temp; } /// summary /// 小顶堆调整降序排序核心 /// private static void MinHeapAdjust(int[] arr, int parentIndex, int heapLength) { int temp arr[parentIndex]; int leftChild 2 * parentIndex 1; while (leftChild heapLength) { int rightChild leftChild 1; int minChildIndex leftChild; if (rightChild heapLength arr[rightChild] arr[leftChild]) { minChildIndex rightChild; } if (temp arr[minChildIndex]) { break; } arr[parentIndex] arr[minChildIndex]; parentIndex minChildIndex; leftChild 2 * parentIndex 1; } arr[parentIndex] temp; } /// summary /// 堆排序升序大顶堆实现 /// public static void SortAsc(int[] arr) { if (arr null || arr.Length 1) return; // 1. 初始化大顶堆从最后一个非叶子节点向前遍历调整 int len arr.Length; for (int i len / 2 - 1; i 0; i--) { MaxHeapAdjust(arr, i, len); } // 2. 迭代交换堆顶与末尾元素逐步排序 for (int i len - 1; i 0; i--) { // 交换堆顶最大值和当前末尾元素 (arr[0], arr[i]) (arr[i], arr[0]); // 缩小堆范围重新调整堆顶 MaxHeapAdjust(arr, 0, i); } } /// summary /// 堆排序降序小顶堆实现 /// public static void SortDesc(int[] arr) { if (arr null || arr.Length 1) return; int len arr.Length; // 初始化小顶堆 for (int i len / 2 - 1; i 0; i--) { MinHeapAdjust(arr, i, len); } // 迭代排序 for (int i len - 1; i 0; i--) { (arr[0], arr[i]) (arr[i], arr[0]); MinHeapAdjust(arr, 0, i); } } } class Program { static void Main(string[] args) { // 测试数组 int[] arr1 { 4, 6, 8, 5, 9, 2, 7, 1, 3 }; int[] arr2 (int[])arr1.Clone(); Console.WriteLine(【原始数组】); Console.WriteLine(string.Join(, , arr1)); // 升序测试 HeapSort.SortAsc(arr1); Console.WriteLine(\n【堆排序升序结果】); Console.WriteLine(string.Join(, , arr1)); // 降序测试 HeapSort.SortDesc(arr2); Console.WriteLine(\n【堆排序降序结果】); Console.WriteLine(string.Join(, , arr2)); Console.ReadKey(); } } }代码核心说明纯原生实现基于.NET原生代码开发不依赖任何NuGet包或第三方库全面兼容各.NET版本模块化设计将堆调整、建堆、迭代排序拆分为独立模块逻辑层次分明易于理解和二次开发双排序支持同时提供升序和降序两种排序逻辑灵活适应各类业务需求鲁棒性保障内置空值检查和长度校验机制确保代码稳定性可直接集成到生产环境。堆排序优缺点优点性能稳定高效时间复杂度和空间复杂度均达到最优时间复杂度恒为最坏/平均/最好情况一致空间复杂度仅原地排序对比优势快速排序最坏情况为归并排序需要辅助空间内存利用率高完全在原数组上操作仅需少量临时变量典型实现通过数组下标模拟完全二叉树结构适用场景嵌入式系统、内存受限设备如物联网设备海量数据处理能力支持外部排序External Sorting可分批次处理如每次读取1GB数据建堆配合磁盘I/O典型应用100TB数据排序内存仅16GB的服务器场景TopK问题最优解构建大小为K的堆求最大K用小顶堆最小K用大顶堆时间复杂度优化为典型案例热搜排行榜实时计算缺点稳定性不足堆调整会破坏相同元素的原始相对顺序示例学生成绩单同分排序时原始名次会被打乱对比归并排序是稳定的算法实际性能劣势每次堆调整平均需要次比较和交换实测比快速排序慢2-3倍CPU缓存不友好具体表现对个整数的排序快排约0.5秒堆排约1.2秒小数据量不适用当n100时性能可能不如简单排序算法原因堆构建和调整的开销占比过大优化方案混合排序如Introsort会在小数据量时切换为插入排序适用场景基于堆排序的特性时间复杂度稳定为O(nlogn)、空间复杂度O(1)、非稳定排序其在实际开发、算法实践和工程优化中的主要应用场景如下海量数据排序应用细节适用于数据量超过内存容量的场景如TB级日志、千万级用户行为数据典型实现方式分批处理将大数据分割为内存可处理的块每块用堆排序预处理多路归并使用最小堆大小为归并路数K合并已排序块典型案例Hadoop/Spark等分布式框架的shuffle阶段排序优化TopK极值问题解决方案最大K问题维护大小为K的最小堆当新元素大于堆顶时替换并调整最小K问题维护大小为K的最大堆当新元素小于堆顶时替换并调整性能优势时间复杂度O(nlogK)优于全排序的O(nlogn)常见应用电商平台热销商品Top100实时统计服务器监控中CPU占用率最高的10个进程优先级调度系统工程实现任务调度Linux内核CFS调度器使用红黑树堆的变种管理进程优先级消息队列Kafka/RabbitMQ通过堆实现消息优先级处理动态维护支持O(logn)时间复杂度的优先级元素插入/删除快速排序优化方案混合排序策略主流语言标准库如C STL、Java Collections的实现逻辑默认采用快速排序递归深度超过阈值如glibc的2×log2n时切换堆排序检测到近似有序数据时启用插入排序防退化场景防止攻击者构造特殊输入全相同/有序数据导致快排退化为O(n²)内存受限环境排序特殊需求场景嵌入式设备物联网终端RAM仅几十KB依赖堆排序的原地排序特性算法对比算法空间复杂度稳定性堆排序O(1)否归并排序O(n)是快速排序O(logn)否典型应用工业传感器数据实时处理边缘计算节点的数据预处理总结堆排序作为一种经典的排序算法在性能与资源消耗之间实现了出色平衡。它有效解决了快速排序时间复杂度不稳定和归并排序空间占用大的问题。该算法的核心在于利用完全二叉树的堆结构将极值查找的时间复杂度从线性$$O(n)$$降至对数$$O(\log n)$$从而实现了高效稳定的原地排序。从学习角度看堆排序是掌握完全二叉树、堆结构及算法优化思想的典型案例在面试中它位列十大排序算法的重点考察内容工程实践中则是处理海量数据、TopK问题和优先级调度等场景的底层基础算法。本文采用纯C#实现不依赖任何第三方库逻辑完整且注释详尽读者可直接收藏复用全面掌握堆排序的核心原理与实战应用 每日更新C#数据结构与算法 | 后台开发 | 性能优化实战干货 零基础也能轻松掌握的计算机底层原理 | 面试避坑指南 | 开发流畅秘籍 欢迎在评论区交流算法难题 | 点赞收藏不错过最新内容