这是小弟的源代码。
具体运行例子如下（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小的值，请问有没有更快的算法？
- Java code
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); } }}------解决方案--------------------------------------------------------
quickselect with medians of median