思路阐述：

给定一个长度为 n 的整数数列，以及一个整数 k，请用快速选择算法求出数列从小到大排序后的第 k 个数。

输入格式

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

输出格式

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

数据范围

1≤n≤100000,
1≤k≤n

输入样例：

5 3
2 4 1 5 3

输出样例：

3

时/空限制：1s / 64MB

算法1：java版

import java.io.*;

public class kNum {
    static int N=10010;
    int[] q=new int[N];

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

    public static void main(String[] args) throws IOException {
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        String[] arr=br.readLine().split(" ");
        int n=Integer.parseInt(arr[0]);
        int k=Integer.parseInt(arr[1]);
        String[] ss = br.readLine().split(" ");
        int[] res=new int[n];
        for (int i = 0; i <n ; i++) {
            res[i]=Integer.parseInt(ss[i]);
        }
        System.out.println(quick_sort(res,0,n-1,k));
    }
}

时间复杂度

O(nlog2n)

算法2:c++版

#include<iostream>
using namespace std;

const int N=1e5+10;
int q[N];
int n,k;

int quick_select(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)
    {
        do i++;while(q[i]<x);
        do j--;while(q[j]>x);
        if(i<j) swap(q[i],q[j]);
    }
    int llen=j-l+1;
    if(k<=llen) return quick_select(l,j,k);
    else return quick_select(j+1,r,k-llen);
}

int main()
{ 
    scanf("%d %d",&n,&k);
    for(int i=0;i<n;i++)
        scanf("%d",&q[i]);
    printf("%d",quick_select(0,n-1,k));
    return 0;
}

时间复杂度

O(nlog2n)

算法3:python版（暂未通过，不知原因）

算法思路：

思路：
1、使用快速排序算法，根据k，判断要找的数位于左半区间还是右半区间
2、判断方法为计算左半区间的区间长度，
若k小于等于左半区间长度，则要找的数位于左半区间，此时要找的值为左半区间第k大的值；
若k大于右半区间长度，则要找的数位于右半区间，此时要找的值为右半区间第k−len(左半区间长度)大的值。
3、递归进行选择，当l≥rl≥r时，中止，返回a[l]

代码：

# 分解第一行输入：
n,k=map(int, input().split())
# 分解第二行输入：
q=list(map(int,input().split()))

def quickSort(q,l,r,k):
    if l>=r:
        return q[l]   #
    x=q[l+r>>1]
    i=l-1
    j=r+1
    while i<j:
        i+=1  #
        while q[i]<x:
            i+=1
        j-=1
        while q[j]>x:
            j-=1
        if i<j:
            q[i],q[j]=q[j],q[i]  #

    ###左半区间的区间长度：
    llength=j-l+1

    #递归：
    if k<=llength:
        return quickSort(q,l,j,k)
    else:
        return quickSort(q,j+1,r,k-llength)

res=quickSort(q, 0, n - 1, k)
print(res)