Реализация сортировки слиянием с 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 l oop. Правильный способ сделать это будет:

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, отметьте этот ответ out.

Answer 2

Вы создаете массив с размером r - l + 1

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

Метод слияния будет выполняться с l = 3, m = 3, r = 4 Таким образом, вспомогательный массив имеет размер r - l + 1 = 2 = [0, 0]

Ваш для l oop работает от l..r

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

И вы пытаетесь установить значение от arr[3] до helper[3], что невозможно, потому что helper.length = 2

Это почему возникает ArrayIndexOutOfBoundsException! Вы можете изменить доступ к индексу помощника на i - l

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
    System.arraycopy(arr, l, helper, 0, helper.length);
    int i = l;
    int k = l;
    int j = m + 1;
    while (i <= m && j <= r) {
        if (helper[i - l] <= helper[j - l]) { // <---
            arr[k] = helper[i - l]; // <---
            i++;
        } else {
            arr[k] = helper[j - l]; // <---
            j++;
        }
        k++;
    }

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