-3

我直接从书中复制了这个算法，但是在“这里的错误！！！！！！”处不断收到 ArrayIndexOutOfBoundsException 部分...对于 T[i] = ...

这让我发疯，我需要完成这件事......有人可以建议我如何解决这个问题吗？由于翻译书中的算法，我还评论了其他潜在的错误......

去上班了，一会儿回来。非常感谢您的帮助..

public static int select(int n, int S[], int k)
    {
        return select4(S, 1, n, k);
    }

    public static int select4(int S[], int low, int high, int k)
    {
        int pivotpoint = (low+high)/2;  //the algorithm didn't define "pivotpoint", so I'm assuming I can use anything..
        if(high==low)
            return (S[low]);
        else {
            partition4(S, low, high, pivotpoint);
            if(k==pivotpoint)
                return(S[pivotpoint]);
            else if(k<pivotpoint)
                return(select4(S, low, pivotpoint-1, k));
            else
                return(select4(S, pivotpoint+1, high, k));
        }
    }

    public static void partition4(int S[], int low, int high, int pivotpoint)
    {
        int arraysize = high - low + 1;
        int r = (int)Math.ceil(arraysize/5);  //maybe error because not double?
        int i, j, mark=0, first, last;
        int pivotitem;
        int[] T = new int[r];
        int temp;

        for(i=1; i<=r; i++) {
            first = low + 5*i - 5;
            last = Math.min(low + 5*i - 1, arraysize);
            T[i] = S[(first+last)/2]; //Algorithm says "median of S[first] through S[last]"
//          ^ ERROR HERE!!!!!!!!!!!!
        }

        pivotitem = select(r, T, (int)Math.floor((r+1)/2)); //maybe error because not double?
        j = low;

        for(i=low; i<=high; i++) {
            if(S[i] == pivotitem) {
                temp = S[i];
                S[i] = S[j];
                S[j] = temp;
                mark = j;
                j++;
            }
            else if(S[i] < pivotitem) {
                temp = S[i];
                S[i] = S[j];
                S[j] = temp;
                j++;
            }
        }
        pivotpoint = j-1;
        temp = S[mark];
        S[mark] = S[pivotpoint];
        S[pivotpoint] = temp;
    }
4

1 回答 1

1

您将 T 分配为 0..r-1：

int[] T = new int[r];

然后你逐步完成 1..r

for(i=1; i<=r; i++)
T[i] =
于 2012-03-03T15:16:15.310 回答