快速排序

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

输入格式

第一行包含两个整数 n 和 k。

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

输出格式

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

数据范围

1≤n≤100000,
1≤k≤n

输入样例：

5 3
2 4 1 5 3

输出样例：

3

代码

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {

        //处理输入
        Scanner sc = new Scanner(System.in);
        String[] arr1 = sc.nextLine().split(" ");
        int n = Integer.parseInt(arr1[0]);
        int k = Integer.parseInt(arr1[1]);

        String[] arr2 = sc.nextLine().split(" ");
        int[] arr = new int[arr2.length];
        for (int i = 0; i < arr2.length; i++) {
            arr[i] = Integer.parseInt(arr2[i]);
        }

        //排序
        quickSort(arr,0,arr.length-1);

        //输出
        System.out.println(arr[k-1]);
    }

    public static void quickSort(int[] arr,int l,int r){

        if(l>=r) return;  //递归边界

        int i = l-1,j = r+1,x = arr[l+r >> 1]; //定义双指针和极点
        while (i<j){ //一次排序临界值
            do i++;while (arr[i]<x); //从左往右找一个大于极点的值
            do j--;while (arr[j]>x); //从右往左找一个小于极点的值
            if(i<j) swap(arr,i,j); //交换找到的两个值
        }

        quickSort(arr,l,j); //递归排序极点左边的序列
        quickSort(arr,j+1,r); //递归排序极点右边的序列
    }

    //交换
    public static void swap(int[] arr,int i,int j){
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}