代码

#include <algorithm>
#include <random>

std::mt19937 mt(19937);

void sort(unsigned *a, int n) {
    if (n < 2) return;
	unsigned pivot = a[mt() % n];
    int l = 0, r = n - 1;
    while (l < r) {
        if (l <= pivot) ++ l;
        else if (r > pivot) -- r;
        else std::swap(a[l ++], a[r --]);
    }
    while (l && a[l - 1] == pivot) -- l;
    sort(a, l);
    sort(a + r, n - r);
}

评测结果