P1177 【模板】排序

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100005;
int a[MAXN];

// 快速排序（Lomuto 划分）：把 a[r] 作为 pivot 归位，再递归处理左右两半
void quickSort(int l, int r) {
    if (l >= r) return;
    int pivot = a[r];
    int i = l - 1;                       // a[l..i] 是不大于 pivot 的那一段
    for (int j = l; j < r; j++) {
        if (a[j] <= pivot) {
            i++;
            if (i != j) swap(a[i], a[j]);
        }
    }
    if (i + 1 != r) swap(a[i + 1], a[r]); // pivot 归位到 i+1
    quickSort(l, i);
    quickSort(i + 2, r);
}

int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) cin >> a[i];
    quickSort(0, n - 1);
    for (int i = 0; i < n; i++) {
        if (i) cout << ' ';
        cout << a[i];
    }
    cout << '\n';
    return 0;
}