912.排序数组（堆排序）

题目

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

你必须在 不使用任何内置函数 的情况下解决问题，时间复杂度为 O(nlog(n))，并且空间复杂度尽可能小。

解法

class Solution {void buildMaxHeap(vector<int>& nums) {int n = nums.size();for (int i = (n - 1) / 2; i >= 0; --i) {maxHeapify(nums, i, n);}}void maxHeapify(vector<int>& nums, int i, int n) {while (i * 2 + 1 < n) {// 代表当前 i 节点的左右儿子；// 超出数组大小则代表当前 i 节点为叶子节点，不需要移位int lSon = 2 * i + 1;int rSon = 2 * i + 2;int large = i;if (lSon < n && nums[lSon] > nums[i]) large = lSon;if (rSon < n && nums[rSon] > nums[large]) large = rSon;if (large != i) {swap(nums[i], nums[large]);// 迭代判断对应子节点及其儿子节点的大小关系i = large;} else {break;}}}public:vector<int> sortArray(vector<int>& nums) {// heapSort 堆排序int n = nums.size();// 将数组整理成大根堆buildMaxHeap(nums);for (int i = n - 1; i >= 1; --i) {// 依次弹出最大元素，放到数组最后，当前排序对应数组大小 - 1swap(nums[0], nums[i]);--n;maxHeapify(nums, 0, n);}return nums;}
};

让我们用一个具体的例子来展示你提供的堆排序算法的排序过程。我们用数组 nums = [3, 5, 1, 10, 2] 作为示例。

1. 建立最大堆 (buildMaxHeap)

首先，我们需要将数组构建成一个最大堆：

• 初始数组： [3, 5, 1, 10, 2]

从最后一个非叶子节点开始，依次调用 maxHeapify：

• 对于 i = 1:

  • 左子节点：5，右子节点：10
  • 10 > 5，所以 large 更新为 3（10 的索引）。
  • 交换 nums[1] 和 nums[3]，得到 [3, 10, 1, 5, 2]。
  • 对于 i = 3，没有子节点，不需要再调整。

• 对于 i = 0:

  • 左子节点：10，右子节点：1
  • 10 > 3，所以 large 更新为 1。
  • 交换 nums[0] 和 nums[1]，得到 [10, 3, 1, 5, 2]。
  • 现在 i = 1，左子节点为 5，右子节点为 2。
  • 5 > 3，更新 large 为 3。
  • 交换 nums[1] 和 nums[3]，得到 [10, 5, 1, 3, 2]。
  • 对于 i = 3，没有子节点，不需要再调整。

最大堆完成：

最大堆为 [10, 5, 1, 3, 2]。

2. 堆排序过程

现在我们开始排序：

• 初始数组：[10, 5, 1, 3, 2]

第一轮：

• 交换 nums[0] 和 nums[4]（10 和 2），得到 [2, 5, 1, 3, 10]。
• 调用 maxHeapify 对 i = 0，n = 4：
  • 左子节点：5，右子节点：1。
  • 5 > 2，更新 large 为 1。
  • 交换，得到 [5, 2, 1, 3, 10]。
  • 对于 i = 1，左子节点为 3，更新 large 为 3。
  • 交换，得到 [5, 3, 1, 2, 10]。

第二轮：

• 交换 nums[0] 和 nums[3]（5 和 2），得到 [2, 3, 1, 5, 10]。
• 调用 maxHeapify 对 i = 0，n = 3：
  • 左子节点：3，右子节点：1。
  • 3 > 2，更新 large 为 1。
  • 交换，得到 [3, 2, 1, 5, 10]。

第三轮：

• 交换 nums[0] 和 nums[2]（3 和 1），得到 [1, 2, 3, 5, 10]。
• 调用 maxHeapify 对 i = 0，n = 2：
  • 左子节点：2，无右子节点。
  • 2 > 1，更新 large 为 1。
  • 交换，得到 [2, 1, 3, 5, 10]。

第四轮：

• 交换 nums[0] 和 nums[1]（2 和 1），得到 [1, 2, 3, 5, 10]。
• 此时 n = 1，不需要再调用 maxHeapify。

最终排序结果

经过上述步骤，最终得到的排序结果为 [1, 2, 3, 5, 10]。

通过这个例子，你可以清楚地看到如何通过最大堆的建立和调整，完成堆排序的过程。