Merge

Question

Ok, так что я пытаюсь осуществить слияние своего рода в Java, но я бегу в следующее сообщение об ошибке при расщеплении массива:

Exception in thread "main" java.lang.IllegalArgumentException: 2 > 1 
    at java.util.Arrays.copyOfRange(Arrays.java:3591) 
    at MergeSortS.recMergeSort(MergeSortS.java:26) 
    at MergeSortS.recMergeSort(MergeSortS.java:28) 
    at MergeSortS.mergeSort(MergeSortS.java:17) 
    at MergeSortM.main(MergeSortM.java:16) 
Java Result: 1 
BUILD SUCCESSFUL (total time: 1 second) 

Мой сегмент кода заключается в следующем , пожалуйста, помогите мне определить мой вопрос здесь ... :( Я нарочно закомментирован recMergeSort(right) рекурсивного вызова в конце, потому что я хочу, чтобы исправить recMergeSort(left) вызов ...

public void recMergeSort(int[] tempArray){ 
     if(tempArray.length>1){ 
      int mid=(tempArray.length)/2; 

      int[] left=Arrays.copyOfRange(tempArray,0,mid); 

      int[] right=Arrays.copyOfRange(tempArray,mid+1,tempArray.length-1); 

      recMergeSort(left); 
      //recMergeSort(array, right, mid+1, right.length-1); 
     } 
    } 

EDIT Хорошо, так что я проверил другой сайт и Javadoc на copyOfRange метод, требующий следующее:

Parameters: 
original - the array from which a range is to be copied 
from - the initial index of the range to be copied, **inclusive** 
to - the final index of the range to be copied, **exclusive**. (This index may lie outside the array.) 

После фиксации этого следующим образом:

public void recMergeSort(int[] tempArray){ 
     if(tempArray.length>1){ 
      int mid=(tempArray.length)/2; 

      int[] left=Arrays.copyOfRange(tempArray,0,mid+1); 

      int[] right=Arrays.copyOfRange(tempArray,mid+1,tempArray.length); 

      recMergeSort(left); 
      //recMergeSort(array, right, mid+1, right.length-1); 
     } 
    } 

Я получаю следующее сообщение об ошибке:

Exception in thread "main" java.lang.StackOverflowError 

Пожалуйста, помогите мне исправить эту проблему ... :(

Answer 1

Похоже, вы увязли в Arrays.copyOfRange() методе. Попробуйте этот код вместо:

public void recMergeSort(int[] tempArray){ 
    if (tempArray.length > 1){ 
     int mid=(tempArray.length)/2;          // mid = 2 
     int[] left = Arrays.copyOfRange(tempArray, 0, mid);     // [10, 20] 
     int[] right = Arrays.copyOfRange(tempArray, mid, tempArray.length); // [30, 40, 50] 

     recMergeSort(left); 
     //recMergeSort(array, right, mid+1, right.length-1); 
    } 
} 

Arrays.copyOfRange(array, lowIndex, highIndex) скопирует доступа из lowIndexвключительно и highIndexэксклюзивной. Это означает, что highIndex для левой копии должен быть такой же, что и lowIndex для правильной копии.

Использование:

int[] tempArray = new int[] {10, 20, 30, 40, 50}; 
recMergeSory(tempArray); 

Answer 2

Слишком много рекурсии я думаю. От Java documentation.

Thrown when a stack overflow occurs because an application recurses too deeply.

---

Кстати: Посмотрите, что происходит, когда tempArray.length равна 2.

Ваш код имеет ошибку, я думаю.

int mid=(tempArray.length)/2; //mid equals 1 
//calls with params tempArray, 0, 2 
int[] left=Arrays.copyOfRange(tempArray,0,mid+1); 
//calls with params tempArray, 2, 2 
int[] right=Arrays.copyOfRange(tempArray,mid+1,tempArray.length); 

Последняя проблема. Длина равна 2, второй параметр равен 2, а третий параметр равен 2. Длина возвращаемого массива будет равна 0.

Answer 3

Причина, по которой вы получили java.lang.StackOverflowError, состоит в том, что ваш левый массив никогда не станет массивом размер 1. Если он входит в блок, то это означает, что средний минимум будет равен 1, поскольку tempArray может быть 2 для удовлетворения. Затем, когда вы копируете влево 0-2, вы копируете весь элемент снова влево и вправо пустым

Answer 4

Переполнение стека - проблема, связанная с тем, что для каждого вызова recMergeSort вы создаете два новых массива , Это называется log (n) раз, и заставляет стек заполняться.

Чтобы исправить это можно либо увеличить размер стека (см: What is the maximum depth of the java call stack?), или вы можете реорганизовывать код, чтобы использовать вместо сортировки путем изменения параметров recMergeSort(int[] tempArray) в recMergeSort(int[] unSortedArray, int startIndex, int endIndex).

Для ясности: первый вызов к нему будет recMergeSort(array, 0, array.length-1), который будет затем вызвать recMergeSort(array, startIndex, endIndex/2) и recMergeSort(array, (endIndex/2)+1, endIndex)

Answer 5

После факторинга во всех ошибках, которые вы указали, я получил его работать путем изменения следующим вместе с правками на ОП:

int mid=(tempArray.length-1)/2; 

Благодарим всех вас за поддержку. Я потратил целый день на то, чтобы понять этот беспорядок!