1

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

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 以来已经有一段时间了。

4

1 回答 1

1

System.arraycopy将要复制的元素数作为最后一个参数。在这里，您要从 c 中复制剩余项目的数量，应该是 qj。同样，下一个案例的 pi。

你import java.util.Arrays 在排队package吗？

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

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

于 2013-03-09T16:37:18.590 回答