2 
package merge;
public class Merger {   
int[] a = {1, 10, 5, 9};
// int[] a = {1, 10, 5, 9, 8, 6, 3, 2};
public Merger(){        
    mergSort(a,0,3);        
    for(int i =0; i<a.length;i++){
        //System.out.println(a[i]);
    }
}

private void mergSort(int[] a, int l, int r) {
    if(l>=r){
        return;
    }
    int m=(l+r)/2;      
    mergSort(a,l,m);
    mergSort(a,m+1,r);      
    merge(a,l,m,r);     
}

private void merge(int[] a, int l, int m, int r) {
    int p = l;
    int u = l;
    int v = m + 1;
    int n = (r-l) + 1;
    int[] result = new int[n];
    int s = 0;

    while(p <= r){
        if(u>v){
            s = a[v];
            v = v + 1;
        } else if (v>r){
            s = a[u];
            u = u + 1;
        } else {
            if(a[u]<a[v]){
                s = a[u];
                u = u + 1;
            } else {
                s = a[v];
                v = v + 1;
            }
        }
        result[p] = s;
        p = p + 1;
    }
    copy(result, a, l, r);      
}

private void copy(int[] result, int[] a, int l, int r) {
    for(int i = l; i <= r; i++){
        a[i] = result[i];
    }
}

public static void main(String[] args) {
    Merger m = new Merger();
}

}

我一直在result[p] = s行抛出ArrayIndexOutOfBoundsException。我认为这可能与最终合并有关，但我不确定。当我将结果数组的大小硬编码为数组 a 的大小时，我的程序就可以工作了。我不确定发生了什么。我将不胜感激任何帮助

4

1 回答 1

1

该result数组的大小正确，但您没有正确索引它。您将l其用作起始索引，但数组的第一个可用点位于 0 处，并且l可能大于零。您需要从中减去l索引p才能工作。

result[p-l] = s;

和

for(int i = l; i <= r; i++){
    a[i] = result[i-l];
}
于 2013-09-26T23:36:33.653 回答