文字教学

这道题数据量达1e5，必须用时间复杂度为O(n log n)的算法，这里用快速排序：

1. 选一个基准数（通常选中间位置的数），将数组中比基准小的放左边，大的放右边。
2. 递归处理基准左边和右边的子数组，直到子数组长度为1。 这样就能高效完成排序。

代码

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

int a[100005], n;

void qs(int l, int r) {
    if (l >= r) return;
    int i = l, j = r, mid = a[(l + r) / 2];
    while (i <= j) {
        while (a[i] < mid) i++;
        while (a[j] > mid) j--;
        if (i <= j) {
            swap(a[i], a[j]);
            i++; j--;
        }
    }
    qs(l, j);
    qs(i, r);
}

int main() {
    cin >> n;
    for (int i = 0; i < n; ++i) cin >> a[i];
    qs(0, n - 1);
    for (int i = 0; i < n; ++i) cout << a[i] << " ";
    cout << endl;
    return 0;
}