中国十大网站公司排名,欧模网室内设计网官网,个人网站做捐赠发布违法吗,浙江建设工程信息网高工评选目录 优化堆排序
Java 实例代码
src/runoob/heap/HeapSort.java 文件代码#xff1a; 优化堆排序
上一节的堆排序#xff0c;我们开辟了额外的空间进行构造堆和对堆进行排序。这一小节#xff0c;我们进行优化#xff0c;使用原地堆排序。
对于一个最大堆#xff0c;首…目录 优化堆排序
Java 实例代码
src/runoob/heap/HeapSort.java 文件代码 优化堆排序
上一节的堆排序我们开辟了额外的空间进行构造堆和对堆进行排序。这一小节我们进行优化使用原地堆排序。
对于一个最大堆首先将开始位置数据和数组末尾数值进行交换那么数组末尾就是最大元素然后再对W元素进行 shift down 操作重新生成最大堆然后将新生成的最大数和整个数组倒数第二位置进行交换此时倒数第二位置就是倒数第二大数据这个过程以此类推。
整个过程可以用如下图表示 Java 实例代码
源码包下载Downloadhttps://www.runoob.com/wp-content/uploads/2020/09/runoob-algorithm-HeapSort.zip
src/runoob/heap/HeapSort.java 文件代码
package runoob.heap; import runoob.sort.SortTestHelper; /** * 原地堆排序 */ public class HeapSortT extends Comparable { public static void sort(Comparable[] arr) { int n arr.length; // 注意此时我们的堆是从0开始索引的 // 从(最后一个元素的索引-1)/2开始 // 最后一个元素的索引 n-1 for (int i (n - 1 - 1) / 2; i 0; i--) shiftDown(arr, n, i); for (int i n - 1; i 0; i--) { swap(arr, 0, i); shiftDown(arr, i, 0); } } // 交换堆中索引为i和j的两个元素 private static void swap(Object[] arr, int i, int j) { Object t arr[i]; arr[i] arr[j]; arr[j] t; } // 原始的shiftDown过程 private static void shiftDown(Comparable[] arr, int n, int k) { while (2 * k 1 n) { //左孩子节点 int j 2 * k 1; //右孩子节点比左孩子节点大 if (j 1 n arr[j 1].compareTo(arr[j]) 0) j 1; //比两孩子节点都大 if (arr[k].compareTo(arr[j]) 0) break; //交换原节点和孩子节点的值 swap(arr, k, j); k j; } } // 测试 HeapSort public static void main(String[] args) { int N 100; Integer[] arr SortTestHelper.generateRandomArray(N, 0, 100000); sort(arr); // 将heapify中的数据逐渐使用extractMax取出来 // 取出来的顺序应该是按照从大到小的顺序取出来的 for (int i 0; i N; i) { System.out.print(arr[i] ); } // 确保arr数组是从大到小排列的 for (int i 1; i N; i) assert arr[i - 1] arr[i]; } }
