网站建设技术方案模板下载,全包装修,陈坤做直播在哪个网站,wordpress图片布局堆排序是一种将顺序存储二叉树转化为大顶堆或者小顶堆的排序算法。顺序存储二叉树是一种特殊的二叉树存储方式#xff0c;它将二叉树的节点按照一定的逻辑顺序存储在一个数组中#xff0c;以便快速访问节点。大顶堆#xff1a;父节点的值大于或等于其子节点的值的树#xf… 堆排序是一种将顺序存储二叉树转化为大顶堆或者小顶堆的排序算法。顺序存储二叉树是一种特殊的二叉树存储方式它将二叉树的节点按照一定的逻辑顺序存储在一个数组中以便快速访问节点。大顶堆父节点的值大于或等于其子节点的值的树小顶堆父节点的值小于或等于其子节点的值的树。
package com.example.datastructures.tree;import java.util.Arrays;/*** author maoyouhua* version jdk21** 堆排序,将顺序存储二叉树转化为大顶堆或者小顶堆的排序算法** 顺序存储二叉树是一种特殊的二叉树存储方式它将二叉树的节点按照一定的逻辑顺序存储在一个数组中以便快速访问节点。** 大顶堆父节点的值大于或等于其子节点的值的树 小顶堆父节点的值小于或等于其子节点的值的树*/
public class HeapSort {public static void heapSort(int[] arr){int temp 0;//这个循环执行完最大值在树顶了 较大值也在上部但是无序for (int i arr.length / 2 - 1; i 0 ; i--) {adjustHeap(arr,i, arr.length);}for (int j arr.length - 1; j 0; j--) {temp arr[j];arr[j] arr[0];arr[0] temp;adjustHeap(arr,0, j);}}/**** param arr 待调整的数组* param i 表示非叶子节点在数组中的索引* param length 表示对多少个元素进行调整*/public static void adjustHeap(int[] arr, int i, int length){//获取当前值int temp arr[i];for (int k i * 2 1; k length; k k * 2 1) {if (k 1 length arr[k] arr[k 1]) {k;}if (arr[k] temp) {arr[i] arr[k];i k;} else {break;}}arr[i] temp;}/*** 排序效率测试* 花费时间是11毫秒*/private static void efficiencyTest(){int capacity 80000;int[] arr new int[capacity];for (int i 0; i capacity; i) {arr[i] (int)(Math.random() * 100 * capacity);}long start System.currentTimeMillis();heapSort(arr);long end System.currentTimeMillis();System.out.println(花费时间是 (end - start) 毫秒);}/*** 4 4 9 9* ↙ ↘ ↙ ↘ ↙ ↘ ↙ ↘* 6 8 9 8 4 8 6 8* ↙ ↘ ↙ ↘ ↙ ↘ ↙ ↘* 5 9 5 6 5 6 5 4** 46859 49856 94856 96854** param args*/public static void main(String[] args) {int[] arr {4,6,8,5,9};heapSort(arr);System.out.println(Arrays.toString(arr));efficiencyTest();}
}
