堆排序

先构建大顶堆

下沉操作 左节点 或者右节点 大于父节点 那么互换 ，然后递归子子节点

大顶堆堆顶与数组尾部互换

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 将给定数组排序
     * @param arr int整型一维数组 待排序的数组
     * @return int整型一维数组
     */
    public int[] MySort (int[] arr) {
        // write code here
        int length = arr.length;
        buildHead(arr);
        for(int i=length-1;i>0;i--){
            swap(arr,0,i);
//             length--;
            downJust(arr,0,i);
        }
        return arr;
    }
    
    public void downJust(int[] arr, int parent,int length){
        int large = parent;
        int leftChild = 2*parent +1;
        int rightChile = 2*parent +2;
        if(leftChild<length &&(arr[leftChild]>arr[large])){
            large = leftChild;
        }
        if(rightChile<length &&(arr[rightChile]>arr[large])){
            large = rightChile;
        }
        if(large == parent){
            return;
        }
        if(large != parent){
              swap(arr,large,parent);
               downJust(arr,large,length);
        }
    }
    public void swap(int[] arr,int i,int j){
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
    
    public void buildHead(int[] arr){
        int length = arr.length;
        for(int i = length/2;i>=0;i--){
            downJust(arr,i,length);
        }
        
    }
}