#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 100010;
int q[N], n, sz, w[N];

void insert_sort()
{
    for (int i = 1; i < n; i++) // 从下标为1的元素开始遍历数组
    {
        // t暂时保存当前元素的值,j用于记录当前元素的索引
        int t = q[i], j = i;

        // 如果前面的元素大于当前元素,则后移
        while (j && q[j - 1] > t)
        {
            // 保证插入位置之前的元素都是排好序的
            // 将前面元素后移一个位置
            q[j] = q[j - 1];
            // j前移,继续与前一个元素比较
            j--;
        }
        //找到插入位置后,将t值插入
        q[j] = t;
    }
}   // 对数组从从下标1开始的每个元素,将其插入到有序序列中正确的位置

void binary_search_insert_sort() {  // 折半插入排序

    for (int i = 1; i < n; i ++) {
        if (q[i - 1] <= q[i]) continue;
        int t = q[i];
        int l = 0, r = i - 1;
        while (l < r) {
            int mid = l + r >> 1;
            if (q[mid] > t) r = mid;
            else l = mid + 1;
        }
        for (int j = i - 1; j >= r; j --)
            q[j + 1] = q[j];
        q[r] = t;
    }
}

void bubble_sort() {
   // 冒泡排序
   // 第一层for循环控制趟数
   for (int i = 0; i < n - 1; i ++) {
      bool has_swap = false; // 标记本趟排序是否发生交换

      // 每趟排序从后往前扫描
      for (int j = n - 1; j > i; j --) {

         // 如果前一个数大于后一个数,交换两个数
         if (q[j - 1] > q[j]) { 
            swap(q[j - 1], q[j]);
            has_swap = true; // 本趟有交换,取true
         }
      }

      // 如果本趟没有交换,说明已排完,提前结束排序
      if (!has_swap) break; 
   }
}

//选择排序
void select_sort(){

    for (int i = 0; i < n - 1; i ++) {
        //每次从未排序元素中选出最小的一个与第一个元素交换
        int k = i;  

        for (int j = k + 1; j < n; j ++) 
            //找到从k+1到n-1中的最小元素的下标k
            if (q[j] < q[k]) 
                k = j; 
        //交换q[i]和q[k]的元素
        swap(q[i], q[k]);
    }
}

void shell_sort() {     // 希尔排序

    // 希尔排序的核心是减少元素的增量d,逐步接近直接插入排序
    // 常见的增量序列是:n/2, n/4, n/8, ...

    // for (int d = n / 2; d; d /= 2) {
    for (int d = n / 3; d; d = d == 2 ? 1 : d / 3) { 

        // 从某个增量序列d开始交换
        for (int start = 0; start < d; start ++) {

            //start处的元素作为开始,比较每个元素是否大于其后d个元素
            for (int i = start + d; i < n; i += d) {

                //将i处元素与其前d个位置依次比较交换
                int t = q[i], j = i;
                while (j > start && q[j - d] > t) {
                    q[j] = q[j - d]; 
                    j -= d;
                }
                q[j] = t;
            }
        }
    }
}

void quick_sort(int l, int r) {
   // 快速排序
   // 结束条件
   if (l >= r) return; 

   // 取中值作为基准数
   int i = l - 1, j = r + 1, x = q[l + r >> 1];  

   // 比较并交换元素
   while (i < j) {
      // i 从左向右找,直到遇大于x的数
      do i ++; while (q[i] < x);  

      // j 从右向左找,直到遇小于x的数   
      do j --; while (q[j] > x);

      // 交换
      if (i < j) swap(q[i], q[j]);
   }

   // 分治递归
   quick_sort(l, j); // 左边子列
   quick_sort(j + 1, r); // 右边子列 
}

void up1(int u) {   // 迭代写法

    while (u > 1 && q[u >> 1] < q[u]) {
        swap(q[u >> 1], q[u]);
        u /= 2;
    }
}

void up(int u) {    // 递归写法

    if (u <= 1) return ;

    if (q[u >> 1] < q[u]) {
        swap(q[u >> 1], q[u]);
        up(u >> 1);
    }
}

void down(int u) {  // 递归写法

    int t = u;
    if (u * 2 <= sz && q[u * 2] > q[t]) t = u * 2;
    if (u * 2 + 1 <= sz && q[u * 2 + 1] > q[t]) t = u * 2 + 1;

    if (u != t) {
        swap(q[t], q[u]);
        down(t);
    }
}

void down2(int u) { // 迭代写法

    int t = u;
    if (u * 2 <= sz && q[u * 2] > q[t]) t = u * 2;
    if (u * 2 + 1 <= sz && q[u * 2 + 1] > q[t]) t = u * 2 + 1;

    while (u != t) {
        swap(q[u], q[t]);
        u = t;
        if (u * 2 <= sz && q[u * 2] > q[t]) t = u * 2;
        if (u * 2 + 1 <= sz && q[u * 2 + 1] > q[t]) t = u * 2 + 1;
    }
}

void heap_sort() {      // 堆排序，下标从1开始  
    sz = n;

    for (int i = n >> 1; i; i --) down(i);  // 建个大根堆

    for (int i = 0; i < n - 1; i ++) {
        swap(q[1], q[sz]);
        sz --;
        down2(1);
    }
}

void merge_sort(int l, int r) {     
    // 归并排序

    if (l >= r) return ;  // 如果左右坐标相等,则表示数组只有一个元素,直接返回

    int mid = l + r >> 1; // 计算中间索引

    merge_sort(l, mid); // 递归排序左边部分

    merge_sort(mid + 1, r); // 递归排序右边部分

    int i = l, j = mid + 1, k = 0; // i 和 j 为两个有序序列的索引,k 为合并后数组的索引

    while (i <= mid && j <= r) { // 合并两个有序序列

        if (q[i] <= q[j]) // 如果左边元素小于右边元素
            w[k ++] = q[i ++]; // 就取左边元素放入合并序列

        else  
            w[k ++] = q[j ++]; // 否则取右边元素放入合并序列

    }

    while (i <= mid) // 合并左边剩余元素
        w[k ++] = q[i ++];  

    while (j <= r) // 合并右边剩余元素
        w[k ++] = q[j ++];  

    for (int i = l, j = 0; j < k; i ++, j ++) // 拷贝合并后的数组回原数组
        q[i] = w[j];
}

// 桶排序
// 稳定
void bucket_sort()
{
    for (int i = 0; i < n; i ++) s[q[i]] ++;
    for (int i = 1; i < N; i ++) s[i] += s[i - 1];
    for (int i = n - 1; i >= 0; i --) w[-- s[q[i]]] = q[i];
    for (int i = 0; i < n; i ++) q[i] = w[i];
}

int main() {
    cin >> n;
    for (int i = 1; i <= n; i ++) cin >> q[i];

    // insert_sort();
    // binary_search_insert_sort();
    // bubble_sort();
    // select_sort();
    // shell_sort();
    // quick_sort(0, n - 1);
    heap_sort();
    // merge_sort(0, n - 1);

    for (int i = 1; i <= n; i ++) cout << q[i] << ' ';

    return 0;
}

堆排序

下标必须从1开始

#include <iostream>

using namespace std;

const int N = 100010;

int q[N], sz, n;

/**
 * down函数:递归下浮元素
 * u为下浮元素下标
 * 查找u的左右孩子哪个最大,将最大的与u交换位置
 * 如果u和孩子交换位置,则对孩子节点继续下滤
*/
void down(int u) {  // 递归写法

    int t = u;

    //找到u的左右孩子中最大的那个下标
    if (u * 2 <= sz && q[u * 2] > q[t]) t = u * 2;
    if (u * 2 + 1 <= sz && q[u * 2 + 1] > q[t]) t = u * 2 + 1;

    if (u != t) {
        swap(q[t], q[u]);
        down(t);        //交换后继续对新下滤的孩子节点下滤
    }
}

/**
 * 堆排序函数
 * 初始建成大顶堆
 * 然后交换堆顶和最后一个元素,堆Size减1
 * 对新的堆顶执行下滤操作
*/
void heap_sort() {      // 堆排序，下标从1开始  
    sz = n;

    for (int i = n >> 1; i; i --) down(i);  // 建个大根堆

    for (int i = 0; i < n - 1; i ++) {
        swap(q[1], q[sz]);
        sz --;
        down(1);
    }
}

int main() {
    cin >> n;
    for (int i = 1; i <= n; i ++) cin >> q[i];

    heap_sort();

    for (int i = 1; i <= n; i ++) cout << q[i] << ' ';

    return 0;
}