java - 消除Java排序比较中的越界错误

Question

我目前正在实现InsertionSort和MergeSort来对它们的操作进行比较，我之前已经实现了MergeSort，但正在尝试我当前的算法教科书中的版本。我在注释标记的行(第 58 行)上遇到数组越界错误，一旦超过它，我会假设也可能在第 60 行。这是书中的算法，但我找不到我的错误来自哪里。代码包含用于测试的简单主方法，包含完整代码，因此可复制且可运行。

package algsortcomp;


public class AlgSortComp {


public static void InsertionSort(int[] data){
    //Sorts given array by Insertion Sort
    //Input: an array data of ints
    //Output: array data sorted in nondecreasing 
    int v, j;
    for (int i = 1; i<data.length; i++){
        v = data[i];
        j = i - 1;
        while (j >= 0 && data[j] > v){
            data[j+1] = data[j--];
        }
        data[j+1]=v;
    }
}

public static void MergeSort(int[] data){
    //Sorts array data by recursive mergesort
    //Input: an array data of ints
    //Output: array data sorted in nondecreasing order
    int dlen = data.length;
    int mid = dlen/2;

    int[] b = new int[mid];
    int[] c = new int[dlen-mid];

    if (dlen > 1){
       System.arraycopy(data, 0, b, 0, mid-1);
       System.arraycopy(data, mid, c, 0, dlen-mid);
       MergeSort(b);
       MergeSort(c);
       Merge(b, c, data);
   }         
}

public static void Merge(int[] b, int[] c, int[] data){
    //Merges two sorted arrays into one sorted array
    //Input: Arrays b and c both sorted
    //Output: Sorted array data of elements b and c.
    int p = b.length, q = c.length, dlen = data.length;
    int i=0, j=0, k=0;
    while (i<p && j<q){
        if (b[i] <= c[j])
            data[k] = b[i++];
        else
            data[k]=c[j++];
        k++;
    }
    if (i == p)
        System.arraycopy(c, j, data, k, dlen-1); //<---currently getting Array out of bounds here, tried replacing with
    else                                         //dlen-k and error is gone but array returned is all [0,0,...,0]
        System.arraycopy(b, i, data, k, dlen-1);
}



public static void main(String[] args) {
    int [] test = {3, 5, 23, 56, 1, 12, 32};
    String arraystr = java.util.Arrays.toString(test);
    System.out.println(arraystr);

    //InsertionSort(test);
    MergeSort(test);
    System.out.println(java.util.Arrays.toString(test));
}

}

类还没人醒，所以我请各位谦虚的人多加留意，以发现我的错误。提前致谢。

编辑:我也忘记了如何通过 Arrays.toString() 调用 java.util.Arrays.toString() 。我尝试导入 java.util.Arrays 但没有成功，而且自从我接触 java/arrays 以来已经有一段时间了。

Answer 1

System.arraycopy 将要复制的元素数量作为最后一个参数。在这里，您想要从 c 复制剩余项目的数量，它应该是 q-j。同样，下一个案例的 p-i。

您是否在package行导入java.util.Arrays之后？

另外，将此 System.arraycopy(data, 0, b, 0, mid-1); 更改为

System.arraycopy(data, 0, b, 0, mid);