A7965.求第 k 小的数

你说得对，但是是不稳定的计数排序。

#include <array>
#include <iostream>
#include <map>
using namespace std;
#define N 5000005 

//快速读 
int read(void) {
	int k = 0; char c = getchar();
	while (c<48 || c>57) c = getchar();
	while (c>47 && c<58) {
		k = k*10-48+c; 
		c = getchar();
	}
	return k;
}

//快速排序 
void quick_sort(array<int, N> &a, int left, int right) {
	if (right <= left) return;
	int l = left, r = right,  pivot = a[left];
	while (l < r) {
		while (a[r]>=pivot && l<r) r--;
		if (l<r) a[l++] = a[r];
		while (a[l]<=pivot && l<r) l++;
		if (l<r) a[r--] = a[l];
	}
	a[l] = pivot;
	quick_sort(a, left, l-1);
	quick_sort(a, r+1, right); 
}

//快速选择 
int quick_select(array<int, N> &a, int left, int right, int k) {
	if (right <= left) return a[right];
	int l = left, r = right,  pivot = a[left];
	while (l < r) {
		while (a[r]>=pivot && l<r) r--;
		if (l<r) a[l++] = a[r];
		while (a[l]<=pivot && l<r) l++;
		if (l<r) a[r--] = a[l];
	}
	a[l] = pivot;
	if (l == k) return a[l];
	if (l > k) return quick_select(a, left, l-1, k);
	if (l < k) return quick_select(a, r+1, right, k); 
}

//计数排序（不稳定，但是也不需要稳定性） 
void counting_sort(array<int, N> &a, int left, int right) {
	static map<int, int> t;
	for (int i=left; i<=right; i++) t[a[i]]++;
	int j=0;
	for (pair<int, int> x:t) {
		for (int i=1; i<=x.second; i++) {
			a[j] = x.first;
			j++;
		}
	}
}

array<int, N> a;
int n, k; 

int main() {
	freopen("input.in", "r", stdin);
	n = read(), k = read();
	for (int i=0; i<n; i++) a[i] = read();
	counting_sort(a, 0, n-1);
	printf("%d", a[k]);
	return 0;
}