堆排序

class Solution{
    public void heapSort(int[] nums) {
        for(int i = 1; i < nums.length; i++) {//升序排列，则建立大顶堆，索引0是最大的数
            int index = i;
            while(index > 0 && nums[(index - 1) / 2] < nums[index]) {//索引i的数上浮
                swap(nums, index, (index - 1) / 2);
                index = (index - 1) / 2;
            }
        }
        for(int i = nums.length - 1; i >= 0; i--) {//大顶堆建好了，每次取索引i与0交换，然后索引i的数排序完成
            swap(nums, 0, i);//把i位置的数交换到堆顶，位置i排序完成
            int index = 0;
            while(index * 2 + 1 < i) {//索引0的数进行下沉
                int child = index * 2 + 1;
                if(index * 2 + 2 < i && nums[index * 2 + 2] > nums[child]) {
                    child++;
                }
                if(nums[child] > nums[index]){
                    swap(nums, index, child);
                    index = child;
                }else {
                    break;
                }
            }
        }
    }
    public void swap(int[] nums, int a, int b) {
        int t = nums[a];
        nums[a] = nums[b];
        nums[b] = t;
    }
}