わたしの部屋

1
class Solution {
2
    public int[] sortArray(int[] nums) {
3
        int n = nums.length;
4

5
        // 自底向上构建大根堆
6
        for (int root = n / 2 - 1; root >= 0; root--) {
7
            maxHeapify(nums, root, n);
8
        }
9

10
        // 依次交换堆顶与未排序部分末尾，并重新调整
11
        for (int tail = n - 1; tail > 0; tail--) {
12
            int temp = nums[0];
13
            nums[0] = nums[tail];
14
            nums[tail] = temp;
15
            maxHeapify(nums, 0, tail);
16
        }
17

18
        return nums;
19
    }
20

21
    private void maxHeapify(int[] heap, int root, int heapSize) {
22
        int largest = root;
23
        while (true) {
24
            int left = 2 * root + 1;
25
            int right = 2 * root + 2;
26

27
            if (left < heapSize && heap[largest] < heap[left]) {
28
                largest = left;
29
            }
30
            if (right < heapSize && heap[largest] < heap[right]) {
31
                largest = right;
32
            }
33

34
            if (largest != root) {
35
                int temp = heap[root];
36
                heap[root] = heap[largest];
37
                heap[largest] = temp;
38
                root = largest;
39
            } else {
40
                break;
41
            }
42
        }
43
    }
44
}

1
class Solution {
2
    public int[] sortArray(int[] nums) {
3
        int n = nums.length;
4
        int[] arr = new int[n + 1];
5
        System.arraycopy(nums, 0, arr, 1, n); // 头部保留 arr[0] = 0 作为占位元素
6

7
        // 构建大根堆，首个非叶子节点为 n / 2
8
        for (int i = n / 2; i > 0; i--) {
9
            maxHeapify(arr, i, n);
10
        }
11

12
        // 排序过程
13
        for (int j = n; j > 0; j--) {
14
            int temp = arr[1];
15
            arr[1] = arr[j];
16
            arr[j] = temp;
17
            maxHeapify(arr, 1, j - 1);
18
        }
19

20
        // 复制回原数组或生成新数组返回
21
        int[] result = new int[n];
22
        System.arraycopy(arr, 1, result, 0, n);
23
        return result;
24
    }
25

26
    private void maxHeapify(int[] arr, int i, int end) {
27
        int j = 2 * i; // 左子节点
28
        while (j <= end) {
29
            if (j + 1 <= end && arr[j + 1] > arr[j]) {
30
                j++; // 选择左右子节点中的较大者
31
            }
32

33
            if (arr[i] < arr[j]) {
34
                int temp = arr[i];
35
                arr[i] = arr[j];
36
                arr[j] = temp;
37
                i = j;
38
                j = 2 * i;
39
            } else {
40
                break;
41
            }
42
        }
43
    }
44
}