堆排序算法实验报告：Java实现与JUnit断言验证

简介本资源是一份面向算法初学者与计算机专业学生的堆排序算法综合实验报告以Java语言实现帮助读者系统掌握堆排序的建堆、调整与排序全过程。压缩包内共1个doc文档约63KB内容涵盖算法流程图、关键代码、复杂度分析、实验环境说明及心得体会结构完整适合作为课程实验报告参考或算法复习资料。文档中详细给出了buildHeap、heapify、heapSort等核心方法的实现并配有isHeap与isSorted等测试用例便于读者对照理解堆的性质与排序验证方法。复杂度部分深入分析了建堆O(n)与重建堆O(nlog₂n)的推导过程指出最好、最坏与平均时间复杂度均为O(nlog₂n)空间复杂度为O(1)同时说明堆排序属于不稳定排序。目前已有3943人学习下载适合需要完成算法实验、准备面试或夯实排序基础的学习者参考。1. 堆排序算法实验报告拆解从流程图到 JUnit 断言一份能直接跑通的 Java 实现很多开发者第一次接触堆排序卡住的不是“堆是什么”而是“代码写完了怎么证明它真的排对了”。这份实验报告给了一个很实在的答案用 JUnit 断言把排序结果和堆性质都验证一遍。项目本身是一份算法分析与设计综合实验报告核心交付物是 Java 实现的堆排序类TestHeapSort里面包含建堆、调整、排序、堆性质校验、有序性校验五个方法外加两个Test用例。它适合正在写算法实验报告的学生、准备面试排序题的开发者以及想找一个“能跑、能验证、能改”的堆排序参考实现的人。下面按“项目是什么 → 怎么跑 → 怎么改”的顺序拆开讲。2. 项目结构与技术选型一个类装下建堆、排序、校验三件事2.1 目录结构与文件清单这份实验报告的资源形态比较轻没有 Maven 或 Gradle 工程就是一个 Java 源文件加一份报告文档。按常见做法导入 IDE 后目录大致是这样HeapSortLab/ ├── src/ │ └── TestHeapSort.java # 核心类排序 校验 测试用例 ├── lib/ │ └── junit-4.x.jar # JUnit 4 依赖用于跑 Test └── report/ └── 实验报告书.md # 流程图、复杂度分析、心得体会TestHeapSort.java里没有main方法入口是 JUnit 的Test。这意味着你不能直接java TestHeapSort跑得用 IDE 的“Run as JUnit Test”或者命令行加 JUnit runner。这一点是新手最容易翻车的地方后面避坑章节会细说。2.2 技术选型为什么是 Java JUnit 4实验环境写的是 Windows 7 旗舰版、Java 语言、个人 PC。选 Java 做算法实验很常见原因是数组操作直观、JUnit 断言写起来短。选 JUnit 4 而不是 JUnit 5从代码里的import static org.junit.Assert.*和Test注解能看出来——JUnit 4 的断言是静态导入Assert类JUnit 5 则是org.junit.jupiter.api.Assertions。这个细节决定了你加依赖时该下哪个 jar 包。堆排序本身是原地排序不需要额外容器所以整个类只依赖一个int[]数组。空间复杂度 O(1) 在代码里体现得很直接swap方法只用了一个临时变量t。这也是报告里强调“只有一个用来交换的暂存单元”的由来。2.3 核心方法职责划分类里五个方法各管一段职责边界清晰方法职责调用关系buildHeap从最后一个非叶节点往前调整建初始大顶堆被heapSort调用heapify对以 i 为根、范围为 [i, j] 的子树做下沉调整被buildHeap、heapSort递归调用heapSort建堆 循环交换堆顶与末尾 重建堆对外主入口isHeap递归校验数组是否满足大顶堆性质被testIsHeap调用isSorted线性扫描校验数组是否升序被heapSortTest调用这里有个容易看漏的点heapify的参数是(a, i, j)第三个参数j是当前堆的有效右边界不是数组长度。排序过程中每轮把堆顶换到末尾后有效范围就缩小一位所以传的是i - 1。理解这个边界才能看懂后面代码里为什么判断条件是left j而不是left a.length。3. 核心代码逐段拆解建堆、下沉、排序的完整链路3.1 建堆为什么从 n/2 - 1 开始public void buildHeap(int[] a) { int n a.length; // n/2 - 1 是最后一个有子节点的元素下标 // 叶子节点本身就是一个合法的堆不需要调整 for (int i n / 2 - 1; i 0; --i) { heapify(a, i, n - 1); // 从下往上逐个让子树变成堆 } }逻辑说明完全二叉树用数组存储时下标i的左孩子是2i1右孩子是2i2。最后一个非叶节点的下标就是n/2 - 1因为再往后的节点2i1已经越界。从它开始往前遍历每次调用heapify都把以i为根的子树调整成大顶堆。由于是从下往上处理到根节点时左右子树已经是堆一次下沉就能让整棵树成堆。参数说明a是待排序数组i是当前要调整的子树根下标n - 1是堆的有效右边界建堆阶段整个数组都有效所以传n - 1。3.2 下沉调整递归找最大孩子并交换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; // 右孩子存在且更大改选右孩子 } if (a[i] a[large]) { // 根比最大孩子小违反大顶堆性质 swap(a, i, large); // 交换根和最大孩子 heapify(a, large, j); // 被换下去的元素可能破坏子树递归调整 } }逻辑说明这是堆排序的核心。先定位左右孩子如果左孩子越界说明当前节点是叶子无需调整。然后在左右孩子里挑出较大的那个和根比较。如果根比孩子小交换并沿着被交换的孩子位置继续递归下沉。递归终止条件是根已经不小于孩子或者沉到叶子。参数说明i是当前子树根j是堆的有效边界排序阶段会逐轮缩小。注意判断用的是left j因为j是闭区间右端left j时左孩子仍然有效。3.3 排序主流程交换堆顶与末尾再重建堆public void heapSort(int[] a) { buildHeap(a); // 建堆后 a[0] 是全局最大值 for (int i a.length - 1; i 0; i--) { swap(a, 0, i); // 把当前最大值换到 i 位置i 及之后有序 heapify(a, 0, i - 1); // 堆范围缩小到 [0, i-1]重新调整根 } }逻辑说明建堆完成后a[0]是最大值。第一轮把它和a[n-1]交换最大值归位到数组末尾然后对[0, n-2]范围重新下沉根节点让次大值浮到堆顶。循环n-1次后整个数组升序。注意循环条件是i 0当只剩一个元素时天然有序不需要再处理。参数说明i既是当前待归位的位置也是堆边界的来源。heapify的第三个参数传i - 1表示堆的有效范围是[0, i-1]。3.4 校验方法isHeap 与 isSorted 怎么写public boolean isHeap(int[] a, int i) { int n a.length; if (i n) { return true; // 空节点视为合法堆 } int left 2 * i 1; int right 2 * i 2; if (left n a[left] a[i]) { // 左孩子比根大违反大顶堆 return false; } if (right n a[right] a[i]) { // 右孩子比根大违反大顶堆 return false; } return isHeap(a, left) isHeap(a, right); // 左右子树也得是堆 } public boolean isSorted(int[] ary) { for (int i 0; i ary.length - 1; i) { if (ary[i] ary[i 1]) { // 出现逆序对说明没排好 return false; } } return true; }逻辑说明isHeap用递归校验大顶堆性质——每个节点都不小于它的孩子。isSorted用一次线性扫描检查相邻元素是否非递减。两个方法都不修改原数组纯粹做断言用。isHeap的递归终止条件是i n即访问到空节点返回 true。参数说明isHeap的i是当前校验的子树根从 0 开始isSorted的ary是待校验数组空数组和单元素数组都会返回 true。3.5 测试用例两个 Test 覆盖堆性质和排序结果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的数组验证排序正确性顺带覆盖了重复值场景。print方法逐行输出方便在控制台肉眼确认。参数说明assertTrue来自org.junit.Assert断言失败会抛AssertionError并终止该测试方法。print用System.out.println逐行打印不是格式化输出看结果时注意每行一个数字。4. 运行与验证从导入 IDE 到看到绿色进度条4.1 环境准备与依赖导入按报告里的环境你需要 JDK1.8 及以上都行和一个带 JUnit 支持的 IDE。如果用 Eclipse 或 IntelliJ IDEA新建 Java 项目后把TestHeapSort.java放进src然后添加 JUnit 4 到构建路径。命令行方式的话编译和运行分开# 编译注意把 junit 和 hamcrest 都加进 classpath javac -cp lib/junit-4.13.2.jar:lib/hamcrest-core-1.3.jar -d out src/TestHeapSort.java # 运行 JUnitJUnitCore 是 JUnit 4 自带的命令行入口 java -cp out:lib/junit-4.13.2.jar:lib/hamcrest-core-1.3.jar org.junit.runner.JUnitCore TestHeapSort参数说明-cp指定类路径Windows 下分隔符是分号;Linux/macOS 下是冒号:。JUnitCore后面跟的是类名不带.java后缀。跑通后会看到OK (2 tests)之类的输出。4.2 预期输出与结果核对heapSortTest里调用了print所以除了 JUnit 的测试结果控制台还会打印排序后的数组。输入{50, 20, 90, 50, 30, 40, 60, 25}排序后应该是25 30 40 50 50 60 90逐行打印。如果你看到的是这个序列说明排序逻辑正确。testIsHeap不打印只断言通过就是绿色。提示如果 JUnit 报NoClassDefFoundError: org/hamcrest/SelfDescribing说明只加了 junit 没加 hamcrest补上 hamcrest-core 即可。4.3 手动验证不用 JUnit 也能跑如果你暂时不想配 JUnit可以临时加一个main方法手动验证public static void main(String[] args) { TestHeapSort t new TestHeapSort(); int[] a {50, 20, 90, 50, 30, 40, 60, 25}; t.heapSort(a); System.out.println(java.util.Arrays.toString(a)); System.out.println(isSorted: t.isSorted(a)); }这样直接java TestHeapSort就能跑输出[25, 30, 40, 50, 50, 60, 90]和isSorted: true。验证完再删掉main不影响原有测试。5. 避坑与常见问题堆排序实验里最容易翻车的五个点5.1 现象排序结果降序了不是升序原因建的是大顶堆但交换后没有正确缩小堆范围或者heapify的边界传错导致最大值反复被换回前面。解决确认heapSort里heapify(a, 0, i - 1)的第三个参数是i - 1不是i也不是a.length - 1。堆范围每轮必须缩小一位。5.2 现象数组里有重复元素时结果不对原因heapify里选最大孩子时用了而不是或者交换条件写反。解决选最大孩子用严格小于判断a[left] a[right]交换条件用a[i] a[large]。重复元素本身不影响大顶堆性质只要比较逻辑正确就能排对。5.3 现象isHeap对合法堆返回 false原因isHeap的判断方向写反了。大顶堆要求根不小于孩子所以违反条件是a[left] a[i]。如果写成a[left] a[i]就会把合法堆判成非法。解决记住大顶堆“上大下小”根比孩子小才是违规。5.4 现象JUnit 测试跑不起来报找不到 Test原因JUnit 版本和导入不匹配。代码用的是 JUnit 4 的org.junit.Test如果项目里配的是 JUnit 5注解包名是org.junit.jupiter.api.Test对不上。解决统一用 JUnit 4或者把导入改成 JUnit 5 并调整断言方式。5.5 现象递归heapify栈溢出原因递归下沉时边界没收敛或者数组本身有环不可能但边界传错会导致无限递归。解决确认heapify里递归调用传的是large和jj在排序过程中逐轮减小递归深度不会超过树高log n。如果栈溢出先检查j是否被错误地传成了固定值。6. 二次开发与改造把实验代码变成能复用的排序工具这份代码作为实验报告是完整的但要放进真实项目里用还有几个改造点值得做。第一个是泛型化。现在只支持int[]如果要做通用排序工具可以改成ComparableT[]或者用Comparator。改造时注意swap和比较逻辑都要跟着改a[i] a[large]要换成compareTo或comparator.compare。第二个是提取接口。把heapSort抽成一个Sorter接口的实现方便和快速排序、归并排序做性能对比。第三个是加边界防护。现在传null或空数组会直接 NPE生产代码里应该在heapSort开头加if (a null || a.length 2) return;。验证改造是否成功我一般会保留原来的两个Test再加一组随机数组的对照测试Test public void randomTest() { java.util.Random r new java.util.Random(42); // 固定种子结果可复现 for (int t 0; t 100; t) { int n r.nextInt(200); int[] a new int[n]; for (int i 0; i n; i) a[i] r.nextInt(1000) - 500; int[] expect a.clone(); java.util.Arrays.sort(expect); // JDK 自带排序作为基准 heapSort(a); assertArrayEquals(expect, a); // 逐元素比对 } }这个测试用固定种子生成 100 组随机数组每组都和Arrays.sort的结果比对。跑通它基本能确认你的堆排序在各种长度、含负数、含重复值的场景下都正确。参数说明r.nextInt(200)控制数组长度在 0 到 199 之间覆盖空数组和单元素r.nextInt(1000) - 500让元素落在[-500, 499]覆盖负数。复杂度这块报告里的分析是对的建堆 O(n)每轮重建 O(log n)共 n-1 轮总时间 O(n log n)最好最坏平均都一样。空间 O(1)不稳定。这些结论在改造后依然成立但如果你改成泛型加Comparator比较开销会变大常数项会上升实测时别惊讶。从那以后我每次写完排序类代码都强制走一遍“随机数组 JDK 基准比对”的流程不管多简单的算法都不跳过。堆排序的边界条件太多肉眼检查容易漏让机器帮你比对最省心。希望帮到你。本文还有配套的精品资源点击获取