简介这份资源是一份面向算法初学者与计算机专业学生的堆排序算法综合实验报告以Java语言实现为主线系统讲解堆排序的完整实现过程。内容涵盖算法流程图、关键代码、复杂度分析、实验环境说明、任务解决方案与心得体会适合正在学习数据结构与算法课程、需要完成实验报告或准备面试复习的读者参考。压缩包内共1个doc文档约63KB集中呈现了建堆、堆调整、排序验证等核心代码与测试用例并给出最好、最坏、平均情况均为O(nlogn)的时间复杂度推导及O(1)空间复杂度结论。目前已有3934人学习下载可帮助读者快速理解堆排序的建堆与筛选逻辑掌握复杂度分析方法并借鉴实验报告的写作结构与排错思路。1. 堆排序算法实验包拆解从流程图到 JUnit 断言一份能直接跑通的 Java 实现如果你正在做算法分析与设计这门课的实验报告或者面试前想快速把堆排序从「背代码」变成「能讲清楚每一步为什么这么写」这份资源值得花时间拆一遍。它是一份完整的 Java 实验工程包含建堆流程图、可运行的TestHeapSort类、JUnit 断言验证以及最好/最差/平均三种情况下的复杂度推导。和网上那些只贴一段heapify就完事的片段不同这份代码把「建堆 → 交换堆顶 → 重建堆」的完整链路串了起来还配了isHeap和isSorted两个校验方法等于自带后悔药——排完能立刻验证结果对不对。适合两类人一是要交实验报告的学生二是想用 Java 把堆排序边界条件彻底摸清的开发者。下面按「资源结构 → 代码逐段拆 → 复杂度怎么算 → 踩坑记录 → 进阶验证」的顺序展开。2. 实验资源结构与建堆流程先搞清楚这份包里有几块东西2.1 资源包含的核心文件与职责划分这份实验包的结构不复杂但每一块都有明确分工。核心是一个TestHeapSort类里面塞了七个方法isHeap负责递归校验当前数组是否满足堆性质heapSort是排序主入口swap做元素交换heapify是下沉调整的核心buildHeap从最后一个非终端节点开始建堆isSorted验证最终有序性print输出结果。另外还有两个Test标注的测试方法分别验证「给定数组是堆」和「排序后数组有序」。方法名职责调用关系buildHeap从 n/2-1 到 0 逐个下沉构建大顶堆被heapSort首先调用heapify对节点 i 做下沉维护堆性质被buildHeap和heapSort调用heapSort建堆后反复交换堆顶与末尾元素主入口isHeap递归校验堆性质测试用isSorted线性校验升序测试用实验环境是 Windows 7 Java硬件 2.66GHz CPU、4GB 内存。这个配置跑堆排序绰绰有余因为堆排序本身空间复杂度只有 O(1)不依赖额外内存。常见做法是直接用 JUnit 4 跑测试不需要额外装构建工具javac编译后java运行即可。2.2 建堆流程图的四个阶段拆解流程图描述的是堆排序的宏观步骤分四段建立初始堆、选出最大元素、调整堆、重复直到堆空。但流程图容易让人忽略一个关键细节——建堆是从下往上、从右往左进行的。也就是说第一个被调整的节点是最后一个非终端节点索引为n/2 - 1而不是根节点。为什么从n/2 - 1开始因为完全二叉树中索引大于n/2 - 1的节点全是叶子节点叶子节点天然满足堆性质不需要调整。从最后一个非终端节点开始往前遍历每次调用heapify时该节点的左右子树已经是堆了所以一次下沉就能把以该节点为根的子树变成堆。这个顺序不能反如果从根开始调整子树还没成堆下沉到一半就断了。建堆完成后数组的第一个元素a[0]就是全局最大值。接下来进入排序阶段把a[0]和a[n-1]交换最大值归位到数组末尾然后对a[0]到a[n-2]重新做一次heapify恢复堆性质重复这个过程 n-1 次整个数组就升序了。注意建堆阶段的时间复杂度是 O(n)不是 O(n log n)。很多人直觉上觉得每个节点下沉最多 log n 层n 个节点就是 n log n但实际上大部分节点靠近底层下沉距离很短求和后收敛到 O(n)。这个点在实验报告的复杂度分析里必须写清楚。3. 关键代码逐段拆heapify 的边界条件才是翻车重灾区3.1 heapify 方法的参数含义与递归逻辑heapify(int[] a, int i, int j)这个方法接收三个参数a是待调整数组i是当前需要下沉的节点索引j是堆的有效边界闭区间。注意j不是数组长度而是当前堆的最后一个元素索引。排序过程中每轮交换后堆的有效范围会缩小 1所以j的值是动态变化的。public void heapify(int[] a, int i, int j) { int left i * 2 1; // 左孩子索引 int right i * 2 2; // 右孩子索引 if (left j) { // 左孩子越界说明 i 是叶子节点 return; } int large left; // 先假设左孩子最大 if (right j a[left] a[right]) { large right; // 右孩子存在且更大更新 large } if (a[i] a[large]) { // 父节点比最大孩子小需要交换 swap(a, i, large); heapify(a, large, j); // 交换后 large 位置可能破坏堆性质递归下沉 } }逻辑说明先算出左右孩子索引如果左孩子越界left j说明当前节点是叶子直接返回。否则在左右孩子中选较大的那个记为large。然后比较父节点a[i]和a[large]如果父节点小交换两者并递归对large位置继续下沉。参数说明j的边界判断用的是left j而不是left j因为j是闭区间上界。右孩子的判断用right j确保右孩子存在才参与比较。这两个边界条件写错一个排序结果就会出问题。3.2 buildHeap 的起始索引为什么是 n/2-1public void buildHeap(int[] a) { int n a.length; for (int i n / 2 - 1; i 0; --i) { heapify(a, i, n - 1); } }逻辑说明从最后一个非终端节点n/2 - 1开始倒序遍历到根节点 0对每个节点执行一次heapify。由于遍历顺序是从下往上每次调整时左右子树已经是堆所以一次下沉就能完成。参数说明n / 2 - 1是最后一个有子节点的元素索引。以长度 8 的数组为例n/2 - 1 3索引 4、5、6、7 都是叶子节点不需要调整。从索引 3 开始往前依次调整索引 3、2、1、0。3.3 heapSort 主流程与 swap 的配合public void heapSort(int[] a) { buildHeap(a); // 建大顶堆a[0] 是最大值 for (int i a.length - 1; i 0; i--) { swap(a, 0, i); // 堆顶最大值换到末尾 heapify(a, 0, i - 1); // 对剩余部分重建堆 } }逻辑说明建堆后a[0]是最大值。循环从n-1递减到 1每轮把a[0]和a[i]交换最大值归位到索引i。然后对a[0]到a[i-1]做一次heapify恢复堆性质。注意heapify的第三个参数是i - 1因为索引i已经有序不再参与堆调整。参数说明循环条件是i 0而不是i 0因为当只剩一个元素时天然有序不需要再处理。heapify的边界传i - 1确保已排序的元素不被纳入堆范围。3.4 JUnit 测试方法怎么用Test public void testIsHeap() { int[] a { 16, 14, 10, 8, 7, 9, 3, 2, 4, 1 }; assertTrue(isHeap(a, 0)); } Test public void heapSortTest() { int[] array {50, 20, 90, 50, 30, 40, 60, 25}; heapSort(array); assertTrue(isSorted(array)); print(array); }逻辑说明testIsHeap用一组已知满足堆性质的数组验证isHeap方法本身是否正确。heapSortTest用一组含重复元素的数组验证排序结果是否升序。注意第二个测试数组里有重复的 50这是有意为之——堆排序不稳定重复元素的相对顺序可能改变但排序结果必须有序。参数说明isHeap从根节点 0 开始递归校验要求每个节点都不小于其左右孩子。isSorted线性扫描只要发现前一个元素大于后一个就返回 false。4. 复杂度分析与实验报告写法最好最差平均为什么都是 O(n log n)4.1 建堆 O(n) 的推导逻辑建堆阶段从n/2 - 1到 0 共约n/2个节点需要调整。但每个节点的下沉距离不同靠近底层的节点下沉距离短靠近根节点的下沉距离长。精确计算时高度为 h 的节点最多下沉 h 层而高度为 h 的节点数量约为n / 2^(h1)。求和Σ (n / 2^(h1)) * h对 h 从 0 到 log n收敛到 O(n)。实验报告里写这段时不要只写结论要把这个求和思路写出来。常见做法是画一棵完全二叉树标注每层节点数和最大下沉距离然后说明求和收敛。4.2 排序阶段 O(n log n) 的推导排序阶段需要执行 n-1 次「交换堆顶 重建堆」。每次重建堆时根节点下沉的最大距离是当前堆高度即⌊log₂i⌋ 1其中 i 是当前堆的元素个数。因此总比较次数为Σ log₂ii 从 2 到 n这个求和的上界是n log₂n。最好、最差、平均三种情况都是 O(n log n)因为堆排序对原始数据的排列状态不敏感。无论输入是已经有序、完全逆序还是随机排列建堆和重建堆的比较次数都在同一个量级。这一点和快速排序不同——快排最差会退化到 O(n²)但堆排序不会。4.3 空间复杂度与稳定性空间复杂度 O(1)因为整个排序过程只用了swap里的一个临时变量t。没有递归栈的额外开销吗heapify是递归实现的递归深度最大为树高log n所以严格来说空间复杂度是 O(log n)。但实验报告里通常写 O(1)因为递归栈开销相对于输入规模可以忽略而且很容易改成迭代版本。稳定性方面堆排序是不稳定的。原因在于交换是跳跃式的堆顶元素和末尾元素交换后相同值的元素可能被打乱相对顺序。实验报告里如果要举例子可以用{50, 20, 90, 50, 30}这组数据排序后两个 50 的原始顺序可能改变。4.4 实验报告复杂度分析部分的写法建议实验报告里「算法的计算复杂度分析」这一节建议按三段写第一段写建堆的时间复杂度推导第二段写排序阶段的时间复杂度推导第三段写空间复杂度和稳定性。每段都要有推导过程不能只写结论。最好、最差、平均三种情况可以合并写因为堆排序三者相同重点说明「为什么相同」——因为堆排序的比较次数只和堆的高度有关和原始数据排列无关。5. 避坑与排查堆排序实验里最容易翻车的五个点5.1 排序结果部分有序末尾几个元素位置不对现象跑完heapSort后数组前面大部分有序但最后几个元素位置明显错误。原因heapify的边界参数j传错了。常见错误是在heapSort循环里传i而不是i - 1导致已经归位的元素被重新纳入堆调整。解决检查heapSort里heapify(a, 0, i - 1)的第三个参数确保已排序部分不参与堆调整。可以在每次heapify后打印a[0]到a[i-1]的范围确认堆边界正确。5.2 isHeap 测试通过但 heapSort 结果不对现象testIsHeap断言通过说明isHeap方法本身没问题但heapSortTest失败。原因buildHeap的起始索引写成了n/2而不是n/2 - 1。n/2是第一个叶子节点的索引从叶子开始调整没有意义而且会漏掉最后一个非终端节点。解决确认buildHeap循环从n / 2 - 1开始。以长度 8 的数组为例n/2 - 1 3索引 3 是最后一个有子节点的元素。5.3 数组含重复元素时排序结果不稳定现象排序后数组确实升序但相同值的元素相对顺序和原始数组不一致。原因堆排序本身不稳定这是算法特性不是代码 bug。交换堆顶和末尾元素时跳跃式交换会打乱相同值的相对顺序。解决如果业务场景要求稳定排序堆排序不适用应该换归并排序或插入排序。如果只是实验报告在复杂度分析里说明「堆排序不稳定」即可。5.4 递归 heapify 导致栈溢出现象对大规模数组比如百万元素排序时抛出StackOverflowError。原因heapify是递归实现递归深度等于树高。虽然树高是 log n但 Java 默认栈深度有限极端情况下可能溢出。解决把heapify改成迭代版本用 while 循环替代递归调用。迭代版本逻辑相同只是把递归下沉改成循环下沉。5.5 JUnit 测试方法没有 Test 注解现象写了测试方法但运行时不执行或者报「No runnable methods」。原因忘记加Test注解或者导入了错误的Test类比如导入了org.junit.jupiter.api.Test但用的是 JUnit 4。解决确认导入的是org.junit.Test并且方法上有Test标注。如果用 Maven检查pom.xml里 JUnit 版本和导入的包是否匹配。6. 进阶验证与性能对比用对数器把堆排序和归并排序拉出来跑一遍实验报告交完之后如果想进一步确认自己对堆排序的理解没问题我一般会写一个对数器把堆排序和 Java 自带的Arrays.sort做对比。具体做法是随机生成不同规模的数组分别用两种方法排序然后逐元素比较结果是否一致。跑上几万组随机数据如果全部通过说明堆排序实现没有边界 bug。public void testAgainstArraysSort() { Random rand new Random(); for (int round 0; round 10000; round) { int len rand.nextInt(100) 1; int[] a new int[len]; int[] b new int[len]; for (int i 0; i len; i) { a[i] rand.nextInt(200) - 100; // 含负数 b[i] a[i]; } heapSort(a); Arrays.sort(b); assertArrayEquals(b, a); // 逐元素比较 } }逻辑说明每轮生成一个长度 1 到 100 的随机数组含负数。复制一份给Arrays.sort作为基准另一份给heapSort。排序后逐元素比较任何一组不一致都会触发断言失败。参数说明rand.nextInt(200) - 100生成 -100 到 99 的随机整数覆盖负数和正数。assertArrayEquals是 JUnit 提供的数组比较方法比手动循环更简洁。除了对数器还可以做一个简单的性能对比生成 10 万个随机整数分别用堆排序和Arrays.sort排序记录耗时。堆排序的耗时通常是Arrays.sort的 3 到 5 倍因为Arrays.sort对基本类型用的是双轴快排常数项更小。但这个对比的意义不在于证明谁快谁慢而在于让你直观感受 O(n log n) 和 O(n log n) 之间的常数差异。还有一个值得做的验证是把heapify改成迭代版本然后用同样的对数器跑一遍确认结果一致。迭代版本的好处是避免递归栈开销对大规模数据更友好。改法很简单把递归调用换成i large然后继续 while 循环。public void heapifyIterative(int[] a, int i, int j) { while (true) { int left i * 2 1; int right i * 2 2; if (left j) break; int large left; if (right j a[left] a[right]) { large right; } if (a[i] a[large]) break; swap(a, i, large); i large; // 继续下沉 } }逻辑说明用 while 循环替代递归每次交换后把i更新为large继续下一轮下沉。退出条件是当前节点已经是叶子left j或者父节点已经不小于最大孩子a[i] a[large]。参数说明j仍然是堆的有效边界含义和递归版本一致。迭代版本的空间复杂度严格为 O(1)没有递归栈开销。从那以后我每次写完排序算法都会先跑一遍对数器再交报告因为人眼检查边界条件真的靠不住。希望帮到你。本文还有配套的精品资源点击获取