第k小的数

要求第k小的数，直接做法就是先通过从小到大排序，取第k个数就可以了，但是这样的平均复杂度至少为O(nlogn)，但是我们可以基于快速排序的划分来处理这个问题，平均时间为O(n)

#include<iostream>
using namespace std;
const int N = 100010;
int n,k;
int a[N];
void visit()
{
    for(int i=0;i<n;i++)
        cout<<a[i]<<" ";
    cout<<endl;
}
int quick_find(int k,int l,int r)
{
    int i=l,j=r;
    int temp=a[l];
    while(i<j){
        while(i<j&&a[j]>=temp)j--;
        a[i]=a[j];
        while(i<j&&a[i]<=temp)i++;
        a[j]=a[i];
    }
    a[i]=temp;
    if(i==k-1)return a[i];
    else if(i>k-1)return quick_find(k,l,i-1);
    else return quick_find(k,i+1,r);
}
int main()
{
    scanf("%d%d",&n,&k);
    for(int i=0;i<n;i++)scanf("%d",&a[i]);
    cout<<quick_find(k,0,n-1);
    return 0;
}