$\huge \color{orange}{成仙之路->}$ $\huge \color{purple}{算法基础课题解}$

可参考： 快速排序

完整代码1： $O(n)$

#include<iostream>

using namespace std;

const int N = 100010;

int n,k,a[N];

int quick_sort(int q[],int l,int r,int k)
{
    if(l>=r) return q[l];

    int i=l-1,j=r+1,x=q[l+r>>1];
    while(i<j)
    {
        while(q[++i]<x);
        while(q[--j]>x);
        if(i<j) swap(q[i],q[j]);
    }

    if(j-l+1>=k) return quick_sort(q,l,j,k);
    return quick_sort(q,j+1,r,k-(j-l+1));
}

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

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

    cout<<quick_sort(a,0,n-1,k)<<endl;

    return 0;
}

完整代码2： $O(nlogn)$

#include<iostream>

using namespace std;

const int N = 100010;

int n,k,a[N];

void quick_sort(int q[],int l,int r)
{
    if(l>=r) return;

    int i=l-1,j=r+1,x=q[(l+r)>>1];
    while(i<j)
    {
        while(q[++i]<x);
        while(q[--j]>x);
        if(i<j) swap(q[i],q[j]);
    }

    quick_sort(q,l,j),quick_sort(q,j+1,r);
}

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

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

    quick_sort(a,0,n-1);

    cout<<a[k-1]<<endl;

    return 0;
}