题解 | #排序#
排序
https://www.nowcoder.com/practice/2baf799ea0594abd974d37139de27896
#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; } } };