用java实现的合并排序算法给出ArrayIndexOutOfBound异常

Question

我重写了一百次，我不断收到 IndexOutOfBound 异常。 如果第一个 for 循环填充左侧数组，这可能是一个问题，但我不知道如何更改逻辑。

线程“main”中的异常 java.lang.ArrayIndexOutOfBoundsException：索引 -1 超出长度 10 的范围 在 mergeSortWithTwist.merge(mergeSortWithTwist.java:57)

我不知道还能做什么，非常感谢任何帮助！

public static void merge(int[] inputArr, int p, int q, int r) {

       int n1 = q-p+1;
       int n2 = r-q;
       int[] leftHalf = new int[n1];
       int[] rightHalf = new int[n2];

       for(int i = 0; i < n1; i++)
           leftHalf[i] = inputArr[p+i-1];

       for(int i = 0; i < n2; i++)
           rightHalf[i] = inputArr[q+i];

       leftHalf[n1+1] = Integer.MAX_VALUE;
       rightHalf[n2+1] = Integer.MAX_VALUE;

       int i = 0;
       int j = 0;
   

       for(int k = 0; k < r; k++) {
           if(leftHalf[i] <= rightHalf[j]){
               inputArr[k] = leftHalf[i];
               i++;
           }
           else {
               inputArr[k] = rightHalf[j];
               j++;
           }
       }

   }

    public static void merge_sort(int[] inputArr, int p, int r) {
        if(p<r) {
            int q = (p + r) / 2;
            merge_sort(inputArr,p,q);
            merge_sort(inputArr,q+1,r);
            merge(inputArr,p,q,r);
        }
    }

Answer 1

有几个问题：

• leftHalf[n1+1] = 

  分配给超出范围的索引。

  leftHalf

  有

  n1

  条目，因此

  n1+1

  甚至

  n1

  都超出范围。

• n1

  和

  n2

  的值由左右分区的大小决定，这很好，但是由于您需要额外的条目来存储

  Integer.MAX_VALUE

  ，因此在定义时需要多分配一个条目

  leftHalf

  和

  rightHalf

  。

• 当

  leftHalf[i] = inputArr[p+i-1];

  为零时，赋值

  inputArr[p-1]

  将计算

  i

  ，但该索引位于左分区之外，甚至可能为 -1（当

  p

  为 0 时），这就是您的值例外是抱怨。这应该是

  inputArr[p+i]

  。同样，下一条语句应该分配一个更大的索引。

• 最终的“合并”循环以错误的

  k

  值开始。这个

  k

  不应该从 0 开始，而应该从

  p

  开始。其次，它不应该在到达r

  之前停止，而应该包括

  r

  。

这是您的

merge

 函数，其中包含针对上述问题的更正：

    public static void merge(int[] inputArr, int p, int q, int r) {
        int n1 = q-p+1;
        int n2 = r-q;
        int[] leftHalf = new int[n1 + 1]; // Corrected: need one extra entry
        int[] rightHalf = new int[n2 + 1]; // Corrected: need one extra entry
        for(int i = 0; i < n1; i++)
            leftHalf[i] = inputArr[p+i]; // Corrected: start at inputArr[p]
        for(int i = 0; i < n2; i++)
            rightHalf[i] = inputArr[q+1+i]; // Corrected: start at inputArr[q+1]
        leftHalf[n1] = Integer.MAX_VALUE; // Corrected: use last slot
        rightHalf[n2] = Integer.MAX_VALUE; // Corrected: use last slot
        int i = 0;
        int j = 0;
        for(int k = p; k <= r; k++) { // Corrected: start at p, end at r
            if(leftHalf[i] <= rightHalf[j]){
                inputArr[k] = leftHalf[i];
                i++;
            }
            else {
                inputArr[k] = rightHalf[j];
                j++;
            }
        }
    }

请注意，所有这些错误都可以通过细致的调试来发现：单步执行代码、设置断点、检查变量，甚至可能打印它们。