题解 | #堆排序#

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 将给定数组排序
     * @param arr int整型一维数组 待排序的数组
     * @return int整型一维数组
     */
    public int[] MySort (int[] arr) {
        // write code here
        if(arr == null || arr.length < 2){
            return arr;
        }
        //创建小根堆
        for(int i = arr.length - 1 ; i >= 0 ; i--){
            heapify(arr,i,arr.length);
        }
        int heapSize = arr.length;
        swap(arr,0,--heapSize);
        while(heapSize > 0){
            heapify(arr,0,heapSize);
            swap(arr,0,--heapSize);
        }
        return arr;
    }
    /**
    * arr中index位置的数能否向下移动
    */
    public void heapify(int[] arr,int index,int heapSize){
        int left = 2 * index + 1;
        while(left < heapSize){
            int largest = left + 1 < heapSize && arr[left + 1] > arr[left] ? left + 1 : left;
            largest = arr[largest] > arr[index] ? largest : index;
            if(largest == index){
                break;
            }
            swap(arr,index,largest);
            index = largest;
            left = 2 * index + 1;
        }
    }
    public void swap(int[] arr,int i,int j){
        if(i==j){
            return;
        }
        arr[i] = arr[i] ^ arr[j];
        arr[j] = arr[i] ^ arr[j];
        arr[i] = arr[i] ^ arr[j];
    }
}