package com.lin.tree_0308; import java.text.SimpleDateFormat; import java.util.Arrays; import java.util.Date; public class HeapSort { public static void main(String[] args) { // int[] arr = {4, 6, 8, 5, 9}; // 随机生成 int[] arr = new int[80000000]; for(int i = 0; i < 80000000; i++) { arr[i] =(int)(Math.random()*8000000); } Date date1 = new Date(); SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss"); String format1 = simpleDateFormat.format(date1); System.out.println("排序前时间为:" + format1); heapSort(arr); Date date2 = new Date(); String format2= simpleDateFormat.format(date2); System.out.println("排序后时间为:" + format2); } // heapSort public static void heapSort(int[] arr) { int temp = 0; // adjustHeap(arr, 1, arr.length); // System.out.println("第一次:" + Arrays.toString(arr)); // // adjustHeap(arr, 0, arr.length); // System.out.println("第二次:" + Arrays.toString(arr)); // 将无序序列建成一个堆,根据升序需求选择大顶堆或小顶堆 for(int j = arr.length/2 -1; j >= 0; j--) { adjustHeap(arr, j, 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); } } // heap /** * * @Description: * @author LinZM * @date 2021-3-11 10:14:16 * @version V1.8 * @param arr 待调整数组 * @param i 表示非叶子节点在数组中的索引 * @param lenght 表示对多少个元素继续调整,逐渐变小 */ public static void adjustHeap(int[] arr, int i, int length) { // 先取出当前元素的值 int temp = arr[i]; // j = 2 * i + 1 j是i节点的左节点 for(int j = i * 2 + 1; j < length; j = j * 2 + 1) { if(j+1 < length && arr[j] < arr[j+1]) {//右子节点大于左子节点 j++;// j指向有子节点 } if(arr[j] > temp) {// 子节点大于父节点 arr[i] = arr[j]; i = j; } else { break; } } arr[i] = temp; } }
仅供参考,有错误还请指出!
有什么想法,评论区留言,互相指教指教。
觉得不错的可以点一下右边的推荐哟