题目描述
给定一个长度为 n 的整数数列,以及一个整数 k,请用快速选择算法求出数列从小到大排序后的第 k 个数。
java 代码
import java.util.*;
public class Main{
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
int length = sc.nextInt();
int num = sc.nextInt();
int[] q = new int[length];
for(int i = 0; i < length; i++){
q[i] = sc.nextInt();
}
quickSearch(0, length - 1, q);
System.out.print(q[num - 1]);
}
public static void quickSearch(int start, int end, int[] q){
if(start == end) return;
int i = start - 1, j = end + 1, x = q[(i + j) / 2];
while(i < j){
do i++; while(q[i] < x);
do j--; while(q[j] > x);
if(i < j){
int temp = q[i];
q[i] = q[j];
q[j] = temp;
}
}
quickSearch(start, j, q);
quickSearch(j + 1, end, q);
}
}