LeetCode912 使用堆排序解决

堆排序

给你一个整数数组 nums，请你将该数组升序排列。
示例 1：
输入：nums = [5,2,3,1]
输出：[1,2,3,5]

示例 2：
输入：nums = [5,1,1,2,0,0]
输出：[0,0,1,1,2,5]

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/sort-an-array
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

public class HeapSort {

    public static void main(String[] args) {
        int[] nums = new int[]{5, 2, 3, 1};
        sortArray(nums);
        for (int i : nums) {
            System.out.println(i);
        }
    }

    public static int[] sortArray(int[] nums) {
        // 由于堆排序第一个元素为空，先做转换，将第一个元素设置为空
        int n = nums.length + 1;
        int[] newNums = new int[n];
        for (int i = 1; i < n; i++) {
            newNums[i] = nums[i - 1];
        }
        // 堆化
        bulidHeap(newNums, n-1);
        // 排序，每次都将堆顶元素与堆尾交换，再自上而下堆化
        int k = n-1;
        while (k > 1) {
            swap(newNums, 1, k);
            k--;
            heapify(newNums, k, 1);
        }
        // 转化结果
        for (int i = 0; i < n - 1; i++) {
            nums[i] = newNums[i + 1];
        }
        return nums;
    }

    /**
     * 对整个数组堆化
     * @param nums 数组
     * @param n 堆中的数据个数，下标为0的不算
     */
    public static void bulidHeap(int[] nums, int n) {
        for (int i = n / 2; i > 0; i--) {
            heapify(nums, n, i);
        }
    }

    /**
     * 对单个元素，自上而下的堆化
     * @param nums 数组
     * @param n 堆中的数据个数，下标为0的不算
     * @param i 元素所在位置
     */
    public static void heapify(int[] nums, int n, int i) {
        while (true) {
            int maxPos = i;
            if (i*2 <= n && nums[i*2] > nums[i]) maxPos = i*2;
            if (i*2+1 <= n && nums[i*2+1] > nums[maxPos]) maxPos = i*2+1;
            if (maxPos == i) return;
            swap(nums, i, maxPos);
            i = maxPos;
        }
    }

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