代码

#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 (a[l] <= pivot) ++ l;
        else if (a[r] > pivot) -- r;
        else std::swap(a[l ++], a[r --]);
    }
    if (a[r] <= pivot) ++ r;
    sort(a + r, n - r);
    l = 0;
    -- r;
    while (l < r) {
        if (a[l] < pivot) ++ l;
        else if (a[r] == pivot) -- r;
        else std::swap(a[l ++], a[r --]);
    }
    if (a[l] != pivot) ++ l;
    sort(a, l);
}

评测结果