日期:2014-05-20  浏览次数:20908 次

求出一个数列的第k小的数,求教
这是小弟的源代码。
具体运行例子如下(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