computer 版 (精华区)

发信人: gutentag ( Bonjour && deeply in LOVE on the web ), 信区: program
标  题: Re: 找第n个最小数
发信站: 听涛站 (2001年10月14日10:36:39 星期天), 站内信件

【Bonjour && deeply in LOVE on the web】  
//用JAVA 写的，手头只有这个
public class find {       
    private static int[] numbers = {5, 6, 3, 2, 4, 7, 1, 9, 8 };
    
    public static void main (String args[ ]){
        System.out.println(find_n_smaller(0, numbers.length-1, numbers, 3));
    } 
//因为JAVA不支持指针操作，所以把参数改成数组元素的起止索引号

    private static int find_n_smaller(int s, int f, int[] num, int n) {
        int j=s, k=s+1, l=f, t;
        while (k<= l) {
            while (num[j]<= num[l] && j< l) l--;
            if (j< l) {t= num[l]; num[l]= num[j]; num[j]= t; j= l--; }
            while (num[j]> num[k] && j> k) k++;
            if (j> k) {t= num[k]; num[k]= num[j]; num[j]= t; j= k++; }
        }
        if (j-s+1== n) return num[j];
        else if (j-s+1> n) return find_n_smaller(s, j-1, num, n);
        else return find_n_smaller(j+1, f, num, n-(j-s+1));
    }  
}


--

                春が来た、春が来た、どこに来た。
                山に来た、郷に来た、野にも来た。

※ 来源:·听涛站 tingtao.dhs.org·[FROM: 匿名天使的家]