堆排序的时间复杂度在O(NlogN)。
//堆排序
#include <bits/stdc++.h>
using namespace std;
const int N = 1e3 + 5;
int a[N] , n;
//向下调整函数
void down(int i) {
//如果需要调整位置，与父节点交换的是子节点中最小的那个
while (i <= n) {
int k = i;
//判断是否比左结点小，是就交换，用k暂存需要交换的节点的位置
if (i * 2 <= n && a[i*2] > a[k]) k = i * 2;
//判断是否比右节点小，是就交换，用k暂存需要交换的节点的位置
if (i * 2 + 1 <= n && a[i*2+1] > a[k]) k = i * 2 + 1;
//如果子节点都比父节点大，此时结束交换
if (k == i) break;
swap(a[k] , a[i]);
i = k;
}
}
//建堆函数
void creat () {
//从最后一个非叶节点到第一个节点依次向下调整
for (int i = n / 2 ; i >= 1 ; i --) down(i);
}
int main () {
//有n个元素
cin >> n;
int m = n;
//输入元素
for (int i = 1 ; i <= n ; i ++) cin >> a[i];
//建大根堆 从下向上调整
//大根堆：所有的父节点都比它的子节点大的堆，也称为最大堆
creat();
//排序
for (int i = n ; i > 1 ; i --) {
//交换最大元素和当前未固定位置的最后一个元素
swap(a[1] , a[i]);
n --;
//下移
down(1);
}
//输出
for (int i = 1 ; i <= m ; i ++) cout << a[i] << " ";
return 0;
}代码的注释写的很详细，若有问题，欢迎指正。
