第k小数

解题思路：

快排：随机选一个数为基准（一般选中间的数）将大于它的放右边，小的放左边。（要把中间数的值存下来，因为仅靠mid来锁定这个基准数，是不够的，他的位置会变。）

• 用快排来解决问题，不同的是对于没用到的一边不用排序。

解题代码：

#include<bits/stdc++.h>
using namespace std;
int a[5000010];
inline int read(){//题目给的输入函数不用管
    int x = 0, f = 1;
    char ch = getchar();
    while(ch < '0' || ch > '9'){
        if (ch == '-')
            f = -1;
        ch = getchar();
    }
    while(ch >= '0' && ch <= '9'){
        x = (x<<1) + (x<<3) + (ch^48);
        ch = getchar();
    }
    return x * f;
}
int find(int l,int r,int k){
	if(l==r) return a[l]; //缩小到最小的出口时，运气差！
	int i=l,j=r;
	int mid=(l+r)/2;
	int x=a[mid];//将基准值保存下来
	while(i<=j){//直到两个指针i,j错过后停止
		while(a[i]<x) i++;//当顺序是对的就往后走
		while(a[j]>x) j--;//当顺序是对的就往前走
		if(i<=j){//已经包含a[j]>=x>=a[i]的意思,存在i>j的情况，所以要再次判断i<=j
			swap(a[i],a[j]);
			i++;j--;
		}
	}
	if(j>=k) return find(l,j,k);//判断k在什么范围，继续在那个范围找，缩小范围
	if(i<=k) return find(i,r,k);
	return a[k];//如果刚好是的话就输出，i,j有两种位置可能：中间夹一个或相邻
}
int main(){
	int T;
	T=read();
	while(T--){
		int n,k,i;
		n=read();k=read();
		for(i=0;i<n;i++){
			a[i]=read();
		}
		int ans=find(0,n-1,k-1);
		printf("%d\n",ans);
	}
	return 0;
}