堆排序

import java.util.Arrays;

public class HeapSort {
    public static void main(String[] args) {
        int[] nums = {5,8,1,5,4,3,0,9};
        heapSort(nums);
        System.out.println(Arrays.toString(nums));
    }
    
    public static void heapSort(int[] nums){
        //默认大根堆
        for (int i = nums.length/2-1; i >= 0; i--) {//找到最后一个非叶子节点，构造大根堆雏形
            adjustHeap(nums,i,nums.length);
        }

		//每次只需要和大根堆的顶进行交换，然后再调整堆
        for (int i = nums.length-1; i > 0; i--) {
            swap(nums,0,i);
            adjustHeap(nums,0,i);
        }
    }
    
    public static void adjustHeap(int[] nums,int tail,int len){
        int temp = nums[tail];//标记待调整的结点
        //循环的含义是每次只访问自己的子节点，比较大小
        for (int i = tail*2+1; i < len; i=i*2+1) {
        	//找到子节点最大的
            if(i+1 < len && nums[i] < nums[i+1])i++;
            //交换
            if(temp < nums[i]){
                nums[tail] = nums[i];
                tail = i;
            }else break;
        }
        //进行最终交换
        nums[tail] = temp;
    }

    public static void swap(int[] nums,int x,int y){
        int temp = nums[x];
        nums[x] = nums[y];
        nums[y] = temp;
    }
}