java - 用Java实现归并排序

Question

我试图使用 java 实现合并排序，但它说:

Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: 3
    at HelloWorld.merge(HelloWorld.java:42)
    at HelloWorld.sort(HelloWorld.java:30)
    at HelloWorld.sort(HelloWorld.java:28)
    at HelloWorld.sort(HelloWorld.java:29)
    at HelloWorld.sort(HelloWorld.java:28)
    at HelloWorld.main(HelloWorld.java:10)

所以我尝试将原始数组复制到合并子例程中的辅助数组中，我认为这是我用于辅助数组的长度搞乱了一切，“r-l+1”不是辅助数组的长度吗？

如果我将 100 作为辅助数组的长度，代码可以工作，但显然当原始数组的大小变大时它就不会工作。

请提前提供帮助并致谢。

public class HelloWorld{

     public static void main(String []args){

         HelloWorld ms = new HelloWorld();
         int arr[] = new int[]{4,3,0,1,3,2,4,20,13,22,10};

         ms.sort(arr, 0, arr.length - 1);

         ms.printArr(arr);

     }

     void printArr(int arr[])
     {
         int n = arr.length;
         for(int i = 0; i<n; i++){
             System.out.print(" "+arr[i]);
         }
     }

     void sort(int arr[], int l, int r)
     {
         if(l<r){
             int m = (l+r)/2;
             sort(arr, l, m);
             sort(arr, m+1, r);
             merge(arr, l, m, r);

         }

     }

     void merge(int arr[], int l, int m, int r)
     {
        //find out helper array length
        int helper[] = new int[r-l+1];
         // Your code here
         for(int i=l; i<=r; i++){
             helper[i] = arr[i];
         }
         int i = l;
         int k = l;
         int j = m+1;
         while(i<=m && j<=r){
             if(helper[i]<=helper[j]){
                 arr[k]=helper[i];
                 i++;
             }else{
                 arr[k]=helper[j];
                 j++;
             }
             k++;
         }

         while(i<=m){
             arr[k]=helper[i];
             i++;
             k++;
         }
     }


}

Answer 1

如果我理解您尝试正确实现合并排序算法的 MERGE 子例程的方式，则您正在将数组的相关部分(从索引 l ，包括在内，到索引 l ，包括在内)复制到辅助数组中，然后使用复制到辅助数组中的数据修改原始数组。

在这种情况下，辅助数组的长度确实应该是 r-l+1 。但是，看看将原始数组部分复制到辅助数组中的代码，您不会偏移 for 中的索引。环形。正确的做法是:

int helper[] = new int[r-l+1];

for (int i = l; i <= r; i++){
    helper[i-l] = arr[i];
}

不要忘记数组是零索引的!

但是，如果您绝对必须复制数组，我确实建议您采用更现代的复制数组的方法。在这种情况下，我认为最适合的是系统调用 System.arraycopy(arr, l, helper, 0, r-l+1) 。如果您想了解有关在 Java 中(完全或部分)复制数组的不同方法的更多信息，请查看 this answer出来。