为什么我的合并排序不起作用？

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++; 
}