代码

#include <algorithm>
#include <ctime>
#include <random>
using namespace std;

template <typename T>
void QSort(int l, int r, T *arr, mt19937 &mtgen)
{
	if (l >= r)
		return;
	uniform_int_distribution<int> dist(0, r - l);
	T pivot = dist(mtgen) + l;
	swap(arr[pivot], arr[l]);
	int i = l, j = r;
	while (i < j)
	{
		while (i < j && arr[j] >= arr[l])
			j--;
		while (i < j && arr[i] <= arr[l])
			i++;
		swap(a[i], (i == j) ? a[l] : a[j]);
	}
	QSort(l, i - 1, arr, mtgen);
	QSort(j + 1, r, arr, mtgen);
}

void sort(unsigned *a, int n)
{
	mt19937 mtgen(time(NULL));
	QSort(1, n, a, mtgen);
}

评测结果