题解 | #排序#

#include <any>
#include <queue>
#include <vector>
class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 将给定数组排序
     * @param arr int整型vector 待排序的数组
     * @return int整型vector
     */
    vector<int> MySort(vector<int>& a) {
        // write code here
        for (int i = 1; i <= a.size() - 1; ++i) { // 通过插入建堆
            PushUp(a, i + 1);
        }
        for (int i = a.size() - 1; i >= 0; --i) { // 通过删除排序
            swap(a[0], a[i]);
            PushDown(a, i);
        }
        return a;
    }

    // [1, n] 是一个堆，执行下滤操作
    void PushDown(vector<int>& a, int n) {
        int u = 1;
        while (u < n) {
            int l = u * 2, r = u * 2 + 1;
            if (l > n) return; // 没有子树
            if (r > n) { // 没有右子树
                if (a[l - 1] <= a[u - 1]) return; // 左子树较小，停止下滤
                swap(a[u - 1], a[l - 1]);
                u = l;
            } else {
                int maxP = a[l - 1] > a[r - 1] ? l : r; // 选择较大的子树
                if (a[maxP - 1] <= a[u - 1]) return; // 子树较小，停止下滤
                swap(a[u - 1], a[maxP - 1]);
                u = maxP;
            }
        }
    }

    // [1, n] 是一个堆，执行上滤操作
    void PushUp(vector<int>& a, int n) {
        int u = n;
        while (u > 1) {
            int p = u / 2;
            if (a[p - 1] >= a[u - 1]) return; // 父节点较大，停止上滤
            swap(a[p - 1], a[u - 1]);
            u = p;
        }
    }
};