Java数据结构《堆排序》构建大堆顶实现升序排序

Java数据结构《堆排序》构建大堆顶实现升序排序

package tree;

public class HeapSort {
    public static void main(String[] args) {
        int[] arr = {1,2,3,4,5,0,-7,100,-20};
        heapSort(arr);
        for (int i = 0; i < arr.length; i++) {
            System.out.println(arr[i]);
        }
    }
    //处理的思想是
    public static void heapSort(int[] arr){
        int temp;
        for (int length = arr.length ; length > 1; length--) {
            for (int i = length/2 - 1; i >= 0; i--) {//该树下有多少个非叶子节点，然后从下倒上  从右到左的调整树的结构
                adjust(arr,i,length);
            }
            //在堆顶部获取最大值，和队尾的进行交换，开启下一轮的构建大顶堆
            temp = arr[0];
            arr[0] = arr[length - 1];
            arr[length - 1] = temp;
        }
    }
    public static void adjust(int[] arr, int i, int length){//对i个非叶子节点进行大堆顶调整
        int temp = arr[i];
        for (int j = 2 * i + 1; j < length; j = j * 2 + 1) {
            if ((j + 1) < length && arr[j] < arr[j + 1]){
                j++;
            }
            if (temp < arr[j]){
                arr[i] = arr[j];
                arr[j] = temp;
                temp = arr[i];
            }else {
                break;
            }
        }
    }
}