题目大意

给定数列，求第 $k$ 小的数。

分析

模板题。考虑分治，随便选一个数 $x$，然后把比 $x$ 大的数移到右边，比 $x$ 小的数移到左边。因此得到了数 $x$ 的排位，若恰为第 $k$ 个则返回，否则根据大小在左右寻找。

该算法是不稳定的，期望复杂度 $O(n)$，最坏复杂度 $O(n^2)$。

实际上存在最坏复杂度为 $O(n)$ 的 BFPTR 算法，但因为其常数过大实现复杂而很少应用。

ll nn[5000010], k, n;

ll quicksort(ll l, ll r) {
	ll i = l, j = r;
	ll x = nn[(l + r) / 2];
	while (i <= j) {
		while (nn[j] > x)
			j--;
		while (nn[i] < x)
			i++;
		if (i <= j) {
			swap(nn[i], nn[j]);
			i++, j--;
		}
	}  // l <= j <= i <=r
	if (k <= j)
		return quicksort(l, j);
	else if (k >= i)
		return quicksort(i, r);
	else
		return nn[k + 1];
}

int main() {
	n = rr(), k = rr();
	for (ll i = 1; i <= n; i++)
		scanf("%lld", &nn[i]);
	printf("%lld", quicksort(1, n));
	return 0;
}