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

Question

我有一个分而治之的方法来从数组中找到第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,p,r-1,i);
        }
        return Rand_partition(a,r-1,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,0,a.length-1,7));
    }

    public static  int partition(int a[],int p,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.

Answer 1

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

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

相反,你想要这个:

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

那是因为你a[p..q]分为以下三个部分:

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

你的原始代码处理a[r]和a[p..r-1]案件罚款,但a[r+1..q]通过使用r-1而烦恼.

我也能够纠正和简化partition:

public static  int partition(int a[],int p,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命名约定:

类名应该是名词,大小写混合,每个内部单词的首字母大写.方法应该是动词,在第一个字母小写的大小写混合的情况下,每个内部单词的首字母大写.

相关问题

• 这个陈述有意义吗？(Sun的Java变量命名约定)
  • 不幸的是,上面的命名约定文档有一个明显的错误

关于数组声明

另外,不要养成这样声明数组的习惯:

int x[];

您应该使用类型而不是标识符来放置括号:

int[] x;

相关问题

• 有什么区别Object[] x和Object x[]？
• Java 之间int[] myArray和之间的区别int myArray[]
• 在数组声明int[] k,i和int k[],i
  • 这些声明导致不同的类型i!