[模板题]第K个数

来源：模板题

算法标签：快排,快速选择

题目描述：

思路

快排模板，找K时注意递归

代码

#include<iostream>

using namespace std;

const int N=1E5+10;
int a[N];

int quick_sort_k(int a[],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)
    {
        do i++;while(a[i]<x);
        do j--;while(a[j]>x);
        if(i<j)swap(a[i],a[j]);
    }
    
    int sl=j-l+1;//左半部分的值
    if(k<=sl)return quick_sort_k(a,l,j,k);//递归左半部分
    else return quick_sort_k(a,j+1,r,k-sl);//递归右半部分
}

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