java – 从数组中选择第i个最小元素

发布时间：2020-12-15 04:52:30 所属栏目：Java 来源：网络整理

导读：我有一个分而治之的方法来从数组中找到第i个最小的元素.这是代码： public class rand_select{ public static int Rand_partition(int a[],int p,int q,int i) { //smallest in a[p..q] if ( p==q) return a[p]; int r=partition (a,p,q); int k=r-p+1; if (

我有一个分而治之的方法来从数组中找到第i个最小的元素.这是代码：

public class rand_select{
    public static int Rand_partition(int a[],int p,int q,int i) {
        //smallest in a[p..q]
        if ( p==q) return a[p];
        int r=partition (a,p,q);
        int k=r-p+1;
        if (i==k) return a[r];
        if (i<k){
            return Rand_partition(a,r-1,i);
        }
        return Rand_partition(a,q,i-k);
    }

    public static void main(String[] args) {
        int a[]=new int []{6,10,13,15,8,3,2,12};
        System.out.println(Rand_partition(a,a.length-1,7));
    }

    public static  int partition(int a[],int q) {
        int  m=a[0];
        while (p < q) {
            while (p < q && a[p++] < m) {
                p++;
            }
            while (q > p && a[q--] > m) {
                q--;
            }
            int t = a[p];
            a[p] = a[q];
            a[q] = t;
        }
        int k=0;
        for (int i=0; i < a.length; i++) {
            if ( a[i]==m){
                k=i;
            }
        }
        return k;
    }
}

但是,运行时出现异常：java.lang.ArrayIndexOutOfBoundsException.

解决方法

我能够修复一些错误.一个次要的是这一行：

return Rand_partition(a,i-k);
                           ^

相反,你想要这个：

return Rand_partition(a,r+1,i-k);
                           ^

那是因为您已将[p..q]分为三部分,如下所示：

a[p..r-1],a[r],a[r+1..q]

你的原始代码处理a [r]和[p..r-1]的情况很好,但是通过使用r-1代替a [r 1..q].

我还能够纠正和简化分区：

public static  int partition(int a[],int q){
    int  m=a[p]; // not m[0],you want to partition m[p..q]!!!
    while ( p<q){
        while (p<q && a[p] <m){ // don't do p++ here!
            p++;
        }
        while (q>p && a[q]>m){ // don't do q-- here!
            q--;
        }
        int t=a[p];
        a[p]=a[q];
        a[q]=t;
    }
    return p; // no need to search!!!
}

你的原始代码有无关的p和q–.此外,不需要搜索枢轴所在的位置.这是p和q相遇的地方.

关于命名约定

请关注Java naming conventions：

Class names should be nouns,in mixed case with the first letter of each internal word capitalized. Methods should be verbs,in mixed case with the first letter lowercase,with the first letter of each internal word capitalized.