时间复杂度 $O(2n^2 + n)$

空间复杂度 $O(2n)$

代码：

#include <iostream>
using namespace std;

int a[100005];

template<typename T> void paper_sort(T _a[], int _l, int _r)
{
    T maxn = 0;
    for (int i = _l; i <= _r; i++) maxn = max(maxn, _a[i]);
    int _c = 0;
    const int _N = sizeof(a);
    T _b[_N];
    int _n = _r - _l + 1;
    int cur = 0;
    while (cur < _n)
    {
        T _sh = maxn;
        for (int i = _l; i <= _r; i++)
        {
            _sh = min(_sh, _a[i]);
        }
        for (int i = _l; i <= _r; i++)
        {
            if (_a[i] == _sh)
            {
                _b[++cur] = _a[i];
                _a[i] = maxn + 1;
            }
        }
    }
    for (int i = _l; i <= _r; i++) _a[i] = _b[i];
}

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

相当于先找出最小值，遍历找于最小值相等的数，把找出来的数设为最大值 + 1，以此类推直到所有值都转移到b数组，将b数组的值全都赋给a数组