A30694.序列第k小

时间复杂度 $O(n)$ ，适用于数据规模较大情况

//quick_select用的是快排的思想，快排是全部排，这个是局部排。
#include <iostream>
using namespace std;

int n, k, a[1005];

//数据规模大时可以使用快速读

int quick_select(int a[], int left, int right) {
    //序列长度为1说明已经排好了
	if (left >= right) return a[k];
    //基准值pivot和双指针lr
	int pivot=a[left], l=left, r=right;
    //寻找应该交换的元素
	while (l<r) {
        //先移动r指针，找到要交换到左边的第一个元素
		while (a[r]>=pivot && l<r) r--;
        //再移动l指针，找到要交换到右边的第一个元素
		while (a[l]<=pivot && l<r) l++;
        //交换元素
		swap(a[l], a[r]);
	}
    //循环结束时l=r，把基准值交换到应该在的位置
	swap(a[left], a[l]);
    //如果就是第k小，那么直接返回
    if (l == k) return a[k];
    //如果比第k小大，那么往小的部分寻找
	if (l > k) return quick_select(a, left, l);
    //如果比第k小大，那么往大的部分寻找
	return quick_select(a, l+1, right);
} 

int main(){
    cin >> n >> k;
	for (int i=1; i<=n; i++) cin >> a[i];
	cout << quick_select(a, 1, n);
	return 0;
}