怎样实现堆排序算法

例题：假设有一个整数数组nums，请问如何对它进行堆排序？

分析：我们可以使用堆排序算法来解决这个问题。堆排序是一种选择排序，它利用了堆这种数据结构的特点，将数组看成一个完全二叉树。具体实现时，我们可以先将数组建成一个大根堆，然后将堆顶元素与最后一个元素交换，再调整堆，重复上述过程，直到整个数组有序。

Java代码实现：

public static void heapSort(int[] nums) {
    if (nums == null || nums.length <= 1) {
        return;
    }
    buildHeap(nums);
    for (int i = nums.length - 1; i > 0; i--) {
        swap(nums, 0, i);
        adjustHeap(nums, 0, i);
    }
}

private static void buildHeap(int[] nums) {
    int n = nums.length;
    for (int i = n / 2 - 1; i >= 0; i--) {
        adjustHeap(nums, i, n);
    }
}

private static void adjustHeap(int[] nums, int i, int n) {
    int left = i * 2 + 1;
    int right = i * 2 + 2;
    int maxIndex = i;
    if (left < n && nums[left] > nums[maxIndex]) {
        maxIndex = left;
    }
    if (right < n && nums[right] > nums[maxIndex]) {
        maxIndex = right;
    }
    if (maxIndex != i) {
        swap(nums, i, maxIndex);
        adjustHeap(nums, maxIndex, n);
    }
}

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

代码分析：

• 首先将数组建成一个大根堆。
• 将堆顶元素与最后一个元素交换。
• 调整堆。
• 重复上述过程，直到整个数组有序。