爲什麼我的合併排序不起作用？

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 } 

你的for循環會去k次，k爲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++; 
}