题目描述

给定一个长度为n的整数数列，以及一个整数k，请用快速选择算法求出数列的第k小的数是多少。

输入格式
第一行包含两个整数 n 和 k。

第二行包含 n 个整数（所有整数均在1~109范围内），表示整数数列。

输出格式
输出一个整数，表示数列的第k小数。

数据范围
1≤n≤100000,
1≤k≤n

样例

输入样例：
5 3
2 4 1 5 3
输出样例：
3

算法1

(快速选择) $O(n)$

实际上是2n的复杂度，n(1+1/2+1/4+1/8……)<2n

Java 代码

要点：
针对快排模版的修改，根据k与边界数量的对比，选择一边进行递归，当选择右边时还需重新处理k（将k处理为减去左边界数量的新数值）

 int quick_sort(int []q, int l, int r, int k){
        if(l==r)return q[l];
        int x=q[l],i=l-1,j=r+1;
        while(i<j){
            do i++;while(q[i]<x);
            do j--;while(q[j]>x);
            if(i<j){
                int tmp = q[i];
                q[i]=q[j];
                q[j]=tmp;
            }
        }
        int s1=j-l+1;
        if(k<=s1) return quick_sort(q, l, j, k);
        else return quick_sort(q,j+1,r, k-s1);
    }