八大排序之堆排序

package dataStruct.排序算法;

import java.util.Arrays;


public class 堆排序 {
    public static void main(String[] args) {
        int temp = 0;
        int[] arr= {4,6,8,5,9};
        for (int i = arr.length/2-1; i >= 0 ; i-- ) {
            adjustSort(arr,i,arr.length);
        }
        for (int i = arr.length -1; i > 0 ; i--) {
            temp = arr[i];
            arr[i] = arr[0];
            arr[0] = temp;
            adjustSort(arr,0,i);
        }
        System.out.println(Arrays.toString(arr));
    }
    //堆排序的算法
    public static void heapSort(int[] arr){

    }
    //调整算法

    
    public static void adjustSort(int[] arr,int i,int length){
        int k = 2 * i + 1;//i为非叶子节点，k为非叶子节点的左节点。k+1是右节点
        for (; k < length; k = k*2+1) {
            //数组的每一个非叶子节点为2*i-1；
            //非叶子节点的个数为：arr.length/2+1;
            //1.判断他的非叶子节点和子节点的大小关系
            int temp = 0;
            if (k+1 < length && arr[k] < arr[k+1]){
                k++;//比较i的两个子节点的大小，如果右节点大，k++
            }
            //比较arr[i]和arr[k]的大小，如果arr[k]>arr[i]，则交换这个的位置
            if (arr[k] > arr[i]){
                temp = arr[i];
                arr[i] = arr[k];
                arr[k] = temp;
                //交换完成后，将i的位置编程k,因为下一次比较的时候，
                i = k;
            }else {
                break;
            }

        }
    }
}