java基础算法之堆排序算法

????????堆排序是一种将顺序存储二叉树转化为大顶堆或者小顶堆的排序算法。顺序存储二叉树是一种特殊的二叉树存储方式，它将二叉树的节点按照一定的逻辑顺序存储在一个数组中，以便快速访问节点。大顶堆：父节点的值大于或等于其子节点的值的树，小顶堆：父节点的值小于或等于其子节点的值的树。

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();
    }
}