求出一个数列的第k小的数，求教

Question

这是小弟的源代码。
具体运行例子如下（cmd环境下）：
5 3
1
2
3
4
5
0 0
这串数据的输出是
Data set 1: element 3 is 3
简单来讲就是5是数组长度，3是指第k小的数，然后接下来的n行就是数组的数据，如果读完后以0 0结尾则结束
我这个程序应该没什么问题，但是运行起来非常慢，想指教一下有什么地方可以改进的，譬如：
1.读取数据的方式
我本来是打算用Scanner.nextInt（）的，后来发现非常非常慢，比bufferedreader慢10倍，但是bufferedreader要用parseInt转换，也浪费了不少时间。我想问有没有改进的办法？
2.算法本身
我是用快速排序的思想求出第k小的值，请问有没有更快的算法？import java.util.*;
import java.io.*;
public class select { public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] header = br.readLine().trim().split(" ");
int n = Integer.parseInt(header[0]);
int k = Integer.parseInt(header[1]);
int setNum = 1;

long startTime = System.currentTimeMillis();
while(n!=0){

int[] array = new int[n];
for(int i = 0; i < n; i++){
array[i] = Integer.parseInt(br.readLine());
}

int goal = quickselect(array,0,array.length-1,k);
System.out.println("Data set " + setNum + ": element " + k + " is " + goal);


setNum++;
header = br.readLine().trim().split(" ");
n = Integer.parseInt(header[0]);
k = Integer.parseInt(header[1]);
}
float spentTime = (System.currentTimeMillis()-startTime)/1000f;
System.out.println("Spent time: " + spentTime);
}
public static int partition(int[] list, int left,int right, int pivotIndex){
int pivotValue = list[pivotIndex];
int tmp = list[pivotIndex];
list[pivotIndex] = list[right];
list[right] = tmp;
int storeIndex = left;
for(int i = left; i < right; i ++){
if(list[i]<=pivotValue){
int tmp2 = list[storeIndex];
list[storeIndex] = list[i];
list[i] = tmp2;
storeIndex++;
}
}
tmp = list[right];
list[right] = list[storeIndex];
list[storeIndex] = tmp;
return storeIndex;
}
public static int quickselect(int[] list, int left, int right, int k){
if(left == right){
return list[left];
}
int pivotIndex = (left + right)/2;
int pivotNewIndex = partition(list,left,right,pivotIndex);
int pivotDist = pivotNewIndex - left + 1;
if(pivotDist == k){
return list[pivotNewIndex];
}else if(k < pivotDist){
return quickselect(list,left,pivotNewIndex - 1, k);
}else{
return quickselect(list,pivotNewIndex + 1, right, k - pivotDist);
}
}
}

Answer 1

用APICollections.sort排序吧
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] header = br.readLine().trim().split(" ");
int n = Integer.parseInt(header[0]);
int k = Integer.parseInt(header[1]);
int setNum = 1;
long startTime = System.currentTimeMillis();
while (n != 0) {
List<Integer> array = new ArrayList<Integer>();
for (int i = 0; i < n; i++) {
array.add(Integer.parseInt(br.readLine()));
}
Collections.sort(array);

int goal = array.get(k - 1);
System.out.println("Data set " + setNum + ": element " + k + " is "
+ goal);
setNum++;
header = br.readLine().trim().split(" ");
n = Integer.parseInt(header[0]);
k = Integer.parseInt(header[1]);
}
float spentTime = (System.currentTimeMillis() - startTime) / 1000f;
System.out.println("Spent time: " + spentTime);
}

Answer 2

我的理解是：把数据读完，排序Arrays.sort(...)，根据k获取数组元素，即排序后下标为arr.length - k的那个元素。
不要每读一个数就排序。

Answer 3

quickselect with medians of median