（我记得堆排序复杂度的确是 $O(n\log n)$ 啊）

#include <iostream>
#include <vector>

using namespace std;

vector<int> a;

int n;

void rebuild(int p, vector<int>& arr, int len) {
    int val = arr[p];
    int mx = p, ls = p * 2, rs = p * 2 + 1;
    if (ls <= len && arr[ls] > arr[mx]) mx = ls;
    if (rs <= len && arr[rs] > arr[mx]) mx = rs;
    if (mx != p) {
        swap(arr[p], arr[mx]);
        rebuild(mx, arr, len);
    }
}

void heapsort(vector<int>& arr) {
    int len = arr.size() - 1;
    for (int i = (len - 1) >> 1; i; i--)
        rebuild(i, arr, len);
    for (int i = len; ~(-i); i--) {
        swap(arr[1], arr[i]);
        rebuild(1, arr, len);
    }
}

int main() {
    cin >> n;
    a.push_back((int)NULL);
    for (int i = 1, tmp; i <= n; i++) {
        cin >> tmp;
        a.push_back(tmp);
    } heapsort(a);
    for (int i = 1; i <= n; i++)
        cout << a[i] << ' ';
    return 0;
}