【算法】快速排序拓展举例（Java）

【题目描述】
给定一个长度为 n 的整数数列，以及一个整数 k，请用快速选择算法求出数列从小到大排序后的第 k个数
【输入格式】
第一行包含两个整数 n 和 k
第二行包含 n个整数（所有整数均在 1∼10e9 范围内），表示整数数列。
【输出格式】
输出一个整数，表示数列的第 k 小数。

根据快速排序的原理，获取第k个数，即在快排时，将l >= r的情况输出即可，而在递归处理剩下两段时，可根据k的值判断处理哪一段，从而更快的获取结果

import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int k = sc.nextInt();
        int[] q = new int[n];
        for(int i=0; i
            q[i] = sc.nextInt();
        }
        System.out.print(quicksort(q, 0, n-1, k));
    }
    public static int quicksort(int[] q, int l, int r, int k){
    	//如果l >= r，说明找到了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){
                int t = q[i];
                q[i] = q[j];
                q[j] = t;
            }
        }
        int len = j - l + 1;//得到左边一段数组的长度
        //如果k的值在左边数组长度的范围内，则继续快排左边的一段
        if(k <= len) return quicksort(q, l, j, k);
        //如果k的值在右边数组的范围内，则继续快排右边的一段，注意，此时k的值要减去左边一段的长度
        else return quicksort(q, j+1, r, k - len);
    }
}