Quick Sort (快速排序)



















#include <random>
#include <iostream>
using namespace std;

mt19937 rng;
void quick_sort(int a[], int n) {
	if (n < 2) return;
	int idx = rng() % n, val = a[idx];
	swap(a[idx], a[n - 1]);
	int len = 0;
	for (int i = 0; i < n - 1; i++)
		if (a[i] < val) swap(a[i], a[len++]);
	swap(a[len], a[n - 1]);
	int len2 = len + 1;
	for (int i = len + 1; i < n - 1; i++)
		if (a[i] == val) swap(a[i], a[len2++]);
	quick_sort(a, len), quick_sort(a + len2, n - len2);
}
Select a repo