排序之堆排

package com.zhang.reflection.面试.排序;
public class 堆排序 {
    //交换元素
    public static void swap(int[] arr,int a,int b) {
        int temp=arr[a];
        arr[a]=arr[b];
        arr[b]=temp;
    }
    //调整大顶堆（进士调整过程，建立在大顶堆以构建的基础上）
    public static void adjustHeap(int[] arr,int i,int length) {
        int temp=arr[i];  //先取出当前元素i
        for(int k=i*2+1;k<length;k=k*2+1) {  //从i节点的左子节点开始，也就是2i+1处开始
            if(k+1<length&&arr[k]<arr[k+1]) {  //如果左子节点小于右子节点，k指向右子节点
                k++;
            }
            if(arr[k]>temp) {  //如果子节点大于父节点，将子节点值赋给父节点（不用进行交换）
                arr[i]=arr[k];
                i=k;
            }else {
                break;
            }
        }
        arr[i]=temp;  //将temp值放到最终位置
    }
    public static void sort(int[] arr) {
        //构建大顶堆
        for(int i=arr.length/2-1;i>=0;i--) {
            //从第一个非叶子节点从上至下，从右至左调整结构
            adjustHeap(arr,i,arr.length);
        }
        //调整堆结构+交换堆顶元素与末尾元素
        for(int j=arr.length-1;j>0;j--) {
            swap(arr,0,j);  //将堆顶元素与末尾元素进行交换
            adjustHeap(arr,0,j);  //重新对堆进行调整
        }
    }
    public static void main(String[] args){
        int[] arr = {10,7,2,4,7,62,3,4,2,1,8,9,19};
        sort(arr);
        for (int i = 0; i < arr.length; i++) {
            System.out.println(arr[i]);
        }
    }
}