归并排序导致IndexOutOfBoundsException错误

Question

这段代码从文件中读取一些用例和数组的大小，然后填充一个数组并将其发送到归并排序。
问题是我一直得到“索引超出范围”的错误，这让我很烦恼...

我的调试器在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]); 
            }
        }
    }
}

- teh_ouj

---

步骤一是修复您的Eclipse安装，因为调试器无法在我的Eclipse上工作。 - T.J. Crowder

第二步是展示给我们堆栈跟踪信息以及您在哪里遇到了AIOOB错误。 - pcalcao

Answer 1

你的程序中的“merge”部分有几个错误（不包括NPE显示的错误），首先：

int mid = (last-first)/2;

应该是：

int mid = (last+first)/2;

第二个问题是，结尾处的三个for循环总是在运行，但你只需要在a1/a2的剩余部分上运行。我实现了一个有点不同的方法 - 或许它能帮助解释第二个错误:

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]+" ");
    }
}

- Nir Alfasi

Answer 2

首先，你的temp数组长度少了一个元素：

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

由于last和first都是包含在内的，因此上述应该写成：

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

- NPE

---

抱歉没有早些回复...谢谢NPE，我想我应该更有组织。 - teh_ouj