是一种很巧妙的排序算法。

#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;

class Solution {
public:
    /* 用于构建大顶堆，该函数的作用是下沉 */
    /* i代表以i为根节点形成的二叉树，其根节点i是不符合大顶堆要求的，即i不是最大值 */
    /* 以i左右两个子节点为根节点的子二叉树，是符合大顶堆要求的 */
    /* 此时只有将i节点逐个下沉，直到某个位置，不需要下沉为止 */
    void sink(vector<int> &nums, int i, int heapSize) {
        int l = 2 * i + 1;
        int r = 2 * i + 2;
        int largest = i;
        if (l < heapSize && nums[l] > nums[largest]) {
            largest = l;
        }
        if (r < heapSize && nums[r] > nums[largest]) {
            largest = r;
        }
        if (largest == i) { /* 如果nums[i] > nums[l]，同时nums[i] > nums[r]，l和r为根节点的子二叉树是符合堆条件的，此时以i节点为根节点的二叉树也符合堆的条件，下沉完成 */
            return;
        }
        swap(nums[i], nums[largest]);
        sink(nums, largest, heapSize);
    }

    void maxheapify(vector<int>& nums) {
        for (int i = nums.size() / 2 - 1; i >= 0; i--) {
            sink(nums, i, nums.size());
        }
    }

    vector<int> sortArray(vector<int>& nums) {
        maxheapify(nums);
        int heapSize = nums.size() - 1;
        while (heapSize > 1) {
            swap(nums[0], nums[heapSize - 1]);
            heapSize--;
            sink(nums, 0, heapSize);
        }
        return nums;
    }
};