大顶堆的构造&&堆排序的实现

public class heapsort {

    
    public static void construct_heap(int[] arr,int i,int n){
        int child; //拿到初始第i个的儿子节点
        int tem = arr[i];
        int index= 0;
        for(child = i*2+1;child < n;child = child *2+1){
            index = child;
            if(child < n-1 && arr[child+1] > arr[child]){
                child++;
            }
            int father = (child-1)/2;
            if(arr[child] > tem){
                int temp  = arr[father];
                 arr[father] = arr[child];
                 arr[child] = temp;
            }else{
                //这里为什么可以直接break呢？
                //因为我们构建的堆前提要求是从第i个开始，i后面都已经被构建完成了
                //所以在这里如果发现一个子节点不大于父节点，就说明后面的堆得结构是没问题的，自然就可以直接break啦
                break;
            }

        }

    }

    public static void heapsort(int[] arr){
        int n = arr.length;
        //开始自底向上的构建大顶堆
        for(int i = n/2-1;i>=0;i--){
            construct_heap(arr,i,n);
        }

        //依次交换首尾两个元素的位置，并将数组大小减1
        for(int j=arr.length-1;j>=0;j--){
            int tem = arr[j];
            arr[j] = arr[0];
            arr[0] = tem;
            construct_heap(arr,0,j);
        }
    }

    public static void main(String[] args) {
        int[] arr = {9,8,7,6,5,4,3,2,1};
        heapsort(arr);
        System.out.println(Arrays.toString(arr));
    }

}