第k小的数
Description
现有一个包含n个整数（1<=n<=900000）的无序序列(保证序列内元素各不相同)，输入一个整数k（1<=k<=n）,请用较快的方式找出该序列的第k小数并输出。

Input
多组输入。

首先输入一个数据组数T（1<=T<=100）

接下来是T组数据。

每组数据有两行。

第一行先输入两个整数，n和k。

接下来是一行输入n个由空格分开的互不相同的整数num(1<=num<=90000000)。

Output
对于每组数据，输出该组数据中第k小的数num。

Sample
Input
1
6 4
3 2 5 1 4 6
Output
4

思路：就是快排的思路，不过由于快排最后是一个有序的序列，那么它二分的时候左右两边都需要处理，但是对于这个题目显然只需要处理一边，所以它的时间复杂度低很多，思路就是先二分，然后选择一个数作为基准双指针扫一下，小的放他左边大的放他右边O(n)，然后判断一个中间位置是否等于k，因为前面都比他小，等于直接输出就好了，不等于的话，小于k去左区间找，大于k去右区间找。
代码：

#include<iostream> 
#include<algorithm>
using namespace std;

const int maxn = 1e6 + 10;
typedef long long int ll;
ll n,k,mid;
int a[90000001];
void sloved(int l,int r){
	int temp = a[l];
	while(l < r){
		while(a[r]>temp && l<r)r--;
		a[l]=a[r];
		while(a[l]<temp && l<r)l++;
		a[r]=a[l];
	}
	a[l] = temp;
	if(l == k){
		printf("%lld\n",a[k]);
		return ;
	}
	if(l > k)  sloved(1,l-1);
	else  sloved(l+1,n);
}
int main(){
	int t;
	scanf("%d",&t);
	while(t--){
		scanf("%lld%lld",&n,&k);
		for(int i=1;i<=n;i++)scanf("%lld",&a[i]);
		sloved(1,n);
	}
	return 0;
}