Почему мой тип слияния не работает?

Question

Я попытался использовать сортировку слияния. однако он продолжает выскакивать мне ArrayIndexOutOfBoundsException. Может ли кто-нибудь сообщить мне, почему?

Я полностью смущен. Я что-то пропустил?

public class InversionSearch { 
    public int[] mergeSort(int[] array){ 
     if (array.length == 1) { 
      return array; 
     } 
     int[] first = new int[array.length/2]; 
     int[] second = new int[array.length - first.length]; 

     System.arraycopy(array, 0, first, 0, first.length); 
     System.arraycopy(array, first.length, second, 0, second.length); 

     int[] result = merge(mergeSort(first), mergeSort(second)); 
     return result; 
    } 

    public int[] merge(int[] first, int[] second) { 
     int i = 0; 
     int j = 0; 
     int[] temp = new int[first.length + second.length]; 
     for (int k = 0; k < temp.length; k++) { 
      if (first[i] < second[j]) { 
       temp[k] = first[i]; 
       i++; 
      }else { 
       temp[k] = second[j]; 
       j++; 
      } 
     } 
     return temp; 
    } 

    public static void main(String[] args) { 
     int[] input = {1, 3, 2, 4, 5, 6}; 
     InversionSearch iSearch = new InversionSearch(); 
     iSearch.mergeSort(input); 
    } 

} 

Answer 1

ваш for цикл неправильно

for (int k = 0; k < temp.length; k++) { 
    if (first[i] < second[j]) { 
     temp[k] = first[i]; 
     i++; 
    }else { 
     temp[k] = second[j]; 
     j++; 
    } 
} 

Вы не проверять i и j ли правильный индекс или нет.

что-то вроде

first = { 1, 2, 3, 4 } second = { 5, 6, 7 } 

ваш цикл будет идти в к раз и к 7, после 5 итераций i значение будет 5, и вы получите ArrayIndexOutofBoundException.

правильный способ написать это:

int k=0; 
while(i < first.length && j< second.length){ 
    if (first[i] < second[j]) { 
     temp[k] = first[i]; 
     i++; 
    }else { 
     temp[k] = second[j]; 
     j++; 
    } 
    k++; 
} 

//for corner cases where some elements are left out 
while(i < first.length) { 
    temp[k] = first[i]; 
    k++; 
    i++; 
} 
while(j < second.length) { 
    temp[k] = second[j]; 
    k++; 
    j++; 
}