合併排序給出IndexOutOfBoundsException

Question

代碼從一個文件中讀取一些情況和數組的大小，然後填充數組並將其發送到合併排序。
問題是我總是收到index out of bounds，它正在殺死我......

我的調試器剛剛停止在我的eclipse上工作。

import java.io.File; 
import java.io.FileNotFoundException; 
import java.util.Scanner; 

public class mergesort { 

    public static void mergeSort(int[] array, int first, int last){ 
     int mid; 
     if (first<last){ 
      mid = (last + first)/2; 
      mergeSort(array, first, mid); 
      mergeSort(array, mid+1, last); 
      merge(array, first, last); 
     } 
    } 

    public static void merge(int[] array, int first, int last){ 
     int mid = (last-first)/2; 
     int[] temp = new int[(last-first)]; 
     int a1 = first, a2 = mid + 1, current = 0; 
     while (a1 <=mid && a2<=last){ 
      if (array[a1] <= array[a2]) 
       temp[current++] = array[a1++]; 
      else 
       temp[current++] = array[a2++]; 
     } 
     for (int i = a1; i<=mid; i++) 
      temp[current++] = array[i]; 
     for (int i = a2; i<=last; i++) 
      temp[current++] = array[i]; 
     for (int i =0; i<temp.length; i++) 
      array[first+i] = temp[i]; 
    } 

    public static void main(String[] args) throws FileNotFoundException { 
     File file = new File("sort.in"); 
     Scanner scan = new Scanner(file); 
     int n1 = scan.nextInt(); 
     for (int i = 0; i<n1; i++){ 
      int[] array =new int[scan.nextInt()]; 
      for (int j = 0; j<array.length; j++){ 
       array[j] = scan.nextInt(); 
      } 
      mergeSort(array, 0, (array.length)-1); 
      for (int j = 0; j<array.length; j++){ 
       System.out.println(array[j]); 
      } 
     } 
    } 
} 

Answer 1

對於初學者來說，你temp陣列是一個元素太短：

int[] temp = new int[(last-first)]; 

由於兩個last和first是包容性的，上面應改爲：

int[] temp = new int[last - first + 1]; 

Answer 2

的merge部分你的程序有幾個錯誤（不包括NPE顯示的錯誤），第一個：

int mid = (last-first)/2; 

應該是：

int mid = (last+first)/2; 

二，3 for循環的結束，而不管運行 - 但你應該只在任A1/A2的剩餘部分運行。

我實現了一個有點不同 - 或許它會在解釋第二個bug幫助：

public static void mergeSort(int[] arr, int start, int end){ 
    if(start == end) return; 
    // now the recursive calls: 
    // divide the arr: 
    int middle = (end+start)/2; 
    mergeSort(arr, start, middle); 
    mergeSort(arr, middle+1, end); 
    // now merge (conquer) 
    merge(arr, start, end, middle); 
} 

private static void merge(int[] arr, int start, int end, int middle) { 
    int[] sorted = new int[end-start+1];   
    for(int i=start,j=middle+1,index=0; index < sorted.length;){ 
     if(j<=end && arr[i] > arr[j]){ 
      sorted[index] = arr[j]; 
      j++; index++; 
     } 
     else if (i<=middle){ 
      sorted[index] = arr[i]; 
      i++; index++; 
     } 
     else{ 
      sorted[index] = arr[j]; 
      j++; index++; 
     } 
    } 
    // now copy "sorted" to original array 
    for(int i=start,j=0; i<=end; i++,j++){ 
     arr[i] = sorted[j]; 
    } 
} 

public static void main(String...args){ 
    int[] arr = {4,2,9,6,2,8,1,9,10,15,12,11}; 
    mergeSort(arr, 0, arr.length - 1); 
    for(int i=0; i<arr.length; i++){ 
     System.out.print(arr[i]+" "); 
    } 
}