排序-堆排序

给你一个整数数组 nums，请你将该数组升序排列。

输入：nums = [5,2,3,1]
输出：[1,2,3,5]

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

思路直接看我录制的视频吧 算法-堆排序_哔哩哔哩_bilibili

实现代码如下所示：

class Solution {public int[] sortArray(int[] nums) {if (nums == null || nums.length == 1) {return nums;}headSort(nums);return nums;}private void headSort(int[] nums) {for (int i = (nums.length - 1) / 2; i >=0; i--) {adjustHead(nums, i, nums.length);}for (int i = nums.length - 1; i >0; i--) {int temp = nums[i];nums[i] = nums[0];nums[0] = temp;adjustHead(nums, 0, i);}}private void adjustHead(int[] nums, int parent, int length) {int temp = nums[parent];int maxChildIndex = parent * 2 + 1;while (maxChildIndex < length) {int rightChild = maxChildIndex + 1;if (rightChild < length && nums[rightChild] > nums[maxChildIndex]) {maxChildIndex++;}if (maxChildIndex < length && nums[maxChildIndex] < temp) {break;}nums[parent] = nums[maxChildIndex];parent = maxChildIndex;maxChildIndex = maxChildIndex * 2 + 1;}nums[parent] = temp;}
}