1.思路

一看到要找第k的数就想到先排序，在直接返回第k位就行。时间复杂度为O(nlogn)。那有更加简单的方法吗？答案是肯定有，我们可以想到之前学到的快速排序。回想一下快速排序的过程

①确定分界点x，在区间[ l , r ]随意取一个数

②根据分界点x调整，使得x左边的数都小于等于x，x右边的数都大于等于x （难点）

③递归处理左边和右边

在②中我们使得x左边都小于等于x，x右边都大于等于x，这样不就确认了x的是在数组中排第几个位置吗？这时就可以统计x左边的个数，如果大于等于k就代表第k个数在x的左边，所以这时递归左边区间就行；否则递归右边区间；直到l >= r时，也代表找到了第k个数，直接返回就是答案。

2.代码

import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int k = in.nextInt();
        int[] a = new int[n];
        for(int i = 0; i < n; i++)
            a[i] = in.nextInt();
        System.out.println(quickly_sort(a, 0, n - 1, k));
    }
    public static int quickly_sort(int[] a, int l, int r, int k) {
        if(l >= r) return a[l]; //代表找到了第k个数，直接返回就是答案。
        int x = a[l + r >> 1];  //确定分界点
        int i = l - 1, j = r + 1;   //方便后面统一处理
        while(i < j) {          //使得x左边都小于等于x，右边都大于等于x
            while(a[++i] < x);
            while(a[--j] > x);
            if(i < j) {
                int t = a[i];
                a[i] = a[j];
                a[j] = t;
            }
        }
        int s = j - l + 1;  //计算左区间的个数
        if(s >= k)      //如果左区间个数比k大，代表第k个数在左区间
            return quickly_sort(a, l, j, k);
        else
            return quickly_sort(a, j + 1, r, k - s);
    }
}

3.复杂度分析

• 时间复杂度：O(n)
• 空间复杂度：O(1)