912. 排序数组 #

#include <vector>
using namespace std;

class Solution {
public:
  vector<int> sortArray(vector<int> &nums) {
    // 调用堆排序函数
    heap_sort(nums);
    return nums;
  }

private:
  void heap_sort(vector<int> &arr) {
    int n = arr.size();
    // 构建最大堆
    for (int i = n / 2 - 1; i >= 0; i--) { // 从最后一个非叶子节点开始
      heapify(arr, n, i);
    }
    // 一个个交换元素
    for (int i = n - 1; i > 0; i--) {
      swap(arr[0], arr[i]); // 将当前最大的放到数组末尾
      heapify(arr, i, 0); // 重新对剩下的元素进行堆调整
    }
  }

  void heapify(vector<int> &arr, int n, int i) { // n 表示数组长度，i 表示当前节点下标
    // 第一部分，找到最大值
    int largest = i; // 初始化最大为根
    int left = 2 * i + 1; // 左 = 2*i + 1
    int right = 2 * i + 2; // 右 = 2*i + 2

    // 如果左子节点大于根节点
    if (left < n && arr[left] > arr[largest]) { // left < n 合法性检查
      largest = left;
    }

    // 如果右子节点比最大还大
    if (right < n && arr[right] > arr[largest]) {
      largest = right;
    }

    // 第二部分，将最大值交换到根
    // 如果最大不是根
    if (largest != i) {
      swap(arr[i], arr[largest]);

      // 递归地定义子堆
      heapify(arr, n, largest);
    }
  }
};

/**
 * @param {number[]} nums
 * @return {number[]}
 */
var sortArray = function(nums) {
    const heapify = (nums, n, i) => {
        let left = 2 * i + 1
        let right = 2 * i + 2
        let largest = i

        if (left < n && nums[left] > nums[largest]) {
            largest = left
        }

        if (right < n && nums[right] > nums[largest]) {
            largest = right
        }

        if(largest != i) {
            [nums[largest], nums[i]] = [nums[i], nums[largest]]
            heapify(nums, n, largest)
        }
    }

    const n = nums.length

    for (let i = Math.floor(n / 2) - 1; i >= 0; i--) {
        heapify(nums, n, i)
    }

    for (let i = n - 1; i >= 0; i--) {
        [nums[i], nums[0]] = [nums[0], nums[i]]
        heapify(nums, i, 0)
    }

    return nums
};