1、利用最大堆（大的在栈顶）

#include <stdio.h>
#include <queue>
#include <iostream>
using namespace std;
int main(){

    priority_queue<int,vector<int>,less<int> > big_heap;

    int n ,k;
    cin >> n >> k;
    int num;
    while(big_heap.size() < k)
    {

        cin >> num;
        big_heap.push(num);

    }

    while(cin >> num)
    {
        if( num < big_heap.top())
        {
            big_heap.pop();   
            big_heap.push(num);
        }
    }

    cout << big_heap.top();
    return 0;

}

2、快速选择算法

//返回k-1个版本

#include <stdio.h>
#include <queue>
#include <iostream>
using namespace std;

#define N 100010
int a[N];


void quick_select(int l,int r,int k)
{
    if( l >=r )
        return;
    int i = l-1, j = r + 1,x = a[l+r >> 1];

    while( i < j )
    {
        while(a[++i] < x);
        while(a[--j] > x);
        if( i < j)
            swap(a[i],a[j]);
    }
    if( j - l + 1 >= k)  // j - l + 1表示前半段的数的个数，如果满足大于K个数我们在前半部分递归寻找就可以了
        quick_select(l,j,k);
    else                 // k - (j-l+1) 表示后半部分找 需要减去前半部分的长度
        quick_select(j+1,r, k - (j-l+1) ); 

}

int main()
{
    int n,k;
    cin >> n >> k;

    for(int i = 0; i < n;i++)
    {
        cin >> a[i];
    }

    quick_select(0,n-1,k);
    //最后找到第k个数的位置，因为数组是从0开始的，所以我们需要返回索引为k-1
    cout << a[k-1] << endl;

    // for(int i = 0; i < n;i++)
    // {
    //     cout << a[i] << " ";
    // }
    return 0;
}

直接返回 a[l] 的版本

#include <stdio.h>
#include <queue>
#include <iostream>
using namespace std;

#define N 100010
int a[N];


int quick_select(int l,int r,int k)
{
    if( l >=r )
        return a[l];
    int i = l-1, j = r + 1,x = a[l+r >> 1];

    while( i < j )
    {
        while(a[++i] < x);
        while(a[--j] > x);
        if( i < j)
            swap(a[i],a[j]);
    }
    if( j - l + 1 >= k) 
        return quick_select(l,j,k);
    else
        return quick_select(j+1,r, k - (j-l+1) );

}

int main()
{
    int n,k;
    cin >> n >> k;

    for(int i = 0; i < n;i++)
    {
        cin >> a[i];
    }

    cout << quick_select(0,n-1,k);

    return 0;
}