This is not difficult but I am still careless and got an error.. so the basic idea is to use the quick sort algorithm, but we can only do quick sort on the left part or the right part, because the Kth element must be in only one section of them, so this can save time for us! During recursion, we need to change the value of K and pass it to child functions as we need to constantly narrow the range and decides whether the current range is an end.
$time\ O(nlogn)$
#include<iostream>
using namespace std;
const int N =100010;
int q[N];
int n,k;
void quick_sort(int l,int r,int k)
{
if(l>=r) return;
int x=q[l+r>>1];
int i=l-1,j=r+1;
while(i<j)
{
do i++; while(q[i]<x);
do j--; while(q[j]>x);
if(i<j ) swap(q[i],q[j]);
}
if(j-l+1>=k) quick_sort(l,j,k);
else quick_sort(j+1,r, k-(j-l+1));
}
int main()
{
cin>>n>>k;
for(int i=0;i<n;i++) cin>>q[i];
quick_sort(0,n-1,k);
cout<<q[k-1];
return 0;
}