堆排序算法（流程图、关键代码、复杂度分析）.doc

发布时间：2022-05-29 发布人：admin 分类：说明书资料大小：0.06M 资料格式：doc 举报版权申诉

第1页 / 共6页

第2页 / 共6页

第3页 / 共6页

第4页 / 共6页

第5页 / 共6页

第6页 / 共6页

文本预览

算法分析与设计综合实验报告书评分：____________ 题目：堆排序算法一、实验环境： 1、硬件环境：个人 pc 机， CPU 主频：2.66GHz 内存：4GB 2、软件环境：操作系统：Windows 7(旗舰版) 编程语言：java 二、实验任务解决方案： 1、算法的流程图。建立初始堆 1 / 6

生成最小堆 2 / 6

3 / 6

2、算法实现的关键代码 import static org.junit.Assert.*; import org.junit.Test; public class TestHeapSort { 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 void heapSort(int[] a) { buildHeap(a); for (int i = a.length - 1; i // 首先，建一个堆，此时a[0] 就是最大的元素 > 0; i--) { // 每次"选出"最大的元素，共需要进行 n - 1 次 swap(a, 0, i); heapify(a, 0, i - 1); // 在这之后， i 以及后面的元素都是有序的 // 根元素由于被交换过，所以需要进行一次“调整”, // 让他再变成堆 } } public void swap(int[] a, int i, int j) { int t = a[i]; a[i] = a[j]; a[j] = t; } public void heapify(int[] a, int i, int j) { int left = i * 2 + 1; int right = i * 2 + 2; 4 / 6

if (left > j) { // 没有左子树？那就好了 return; } int large = left; if (right <= j && a[left] < a[right]) { // large 是大的这个 large = right; } if (a[i] < a[large]) { // 根元素比 large 小？交换根和 large swap(a, i, large); heapify(a, large, j); //此时 large 树又可能不是堆了, 那就继续努力:) } } public void buildHeap(int[] a) { int n = a.length; for (int i = n / 2 - 1; i >= 0; --i) { // n / 2 - 1, 就是最后一个有子节点的元素 heapify(a, i, n - 1); // 偶们从这开始，不断调整，直到整个数组变成堆 } } public boolean isSorted(int[] ary) { for (int i = 0; i < ary.length - 1; i++) { if (ary[i] > ary[i + 1]) { return false; } } return true; } @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}; 5 / 6

heapSort(array); assertTrue(isSorted(array)); print(array); } public void print(int[] array) { for (int i=0; i

分享到：

赞收藏

资料库

堆排序算法（流程图、关键代码、复杂度分析）.doc

相关推荐

开发技术

热门标签

最新资料