code

快速排序代码

https://www.acwing.com/problem/content/description/787/

void QuickSort(int q[], int low, int high) {
    // 递归的终止情况
    if (low >= high) return;
    
    // 第一步：分解为子问题
    int pivot = q[low+high>>1], i = low - 1, j = high + 1;
    while (i < j) {
        do ++ i; while (q[i] < pivot);
        do -- j; while (q[j] > pivot);
        if (i < j) swap(q[i], q[j]);
    }
    
    // 第二步：递归处理子问题
    QuickSort(q, low, j);
    QuickSort(q, j + 1, high);

    // 第三步：子问题合并.快排这一步不需要操作，但归并排序的核心在这一步骤
}

堆排序代码

https://www.acwing.com/problem/content/description/787/

#include <iostream>
using namespace std;

const int N = 1e5+10;

int q[N];
int len;

// u 需要往下 down 的节点，m 堆的右边界
void HeapDown(int s, int m) {
   int t = s;
   if (s*2<=m && q[s*2]>q[t]) t = s*2;
   if (s*2+1<=m && q[s*2+1]>q[t]) t = s*2+1;
   if (s != t) {
       swap(q[s], q[t]);
       HeapDown(t, m);
   }
}

int main() {
    cin >> len;
    for (int i = 1; i <= len; ++ i) cin >> q[i];
    
    // 初始化大根堆
    for (int i = len/2; i > 0; -- i) HeapDown(i, len);
    
    // 将堆顶记录逐个放到堆尾
    // 每放一个就需要调整堆，保证堆顶记录为堆中的最大值
    for (int i = len; i > 1; -- i) {
        swap(q[1], q[i]);
        HeapDown(1, i-1);
    }

    for (int i = 1; i <= len; ++ i) cout << q[i] << ' ';
    cout << endl;
    
    return 0;
}