MergeSort - ArraysOutOfBoundsException

Question

正在通过一个免费的在线课程学习排序算法，其中教师使用main()方法来展示如何打印结果。

决定使用JUnit测试而不是main方法。

但是，我得到了以下StackTrace：

java.lang.ArrayIndexOutOfBoundsException: 8
    at MergeSort.sort(MergeSort.java:30)
    at MergeSort.sort(MergeSort.java:14)
    at MergeSort.sort(MergeSort.java:14)
    at MergeSortTest.sort(MergeSortTest.java:14)

MergeSort.java (实际实现)：

import java.util.Arrays;

public class MergeSort {

    public static String sort(int[] array, int[] tmpArray, int lowIndex, int highIndex) {
        int midIndex =0;
        int lowIndex1 = 0;
        int lowIndex2 = 0;
        int i = 0;

        // Divide up sets using recursion
        if (highIndex > lowIndex) {
            midIndex = (highIndex + lowIndex) / 2;
            sort(array, tmpArray, lowIndex, midIndex);
            sort(array, tmpArray, midIndex + 1, highIndex);
        }

        lowIndex1 = lowIndex;
        lowIndex2 = midIndex+1;

        System.arraycopy(array, 0, tmpArray, 0, array.length);

        // Merge elements
        while(lowIndex <= midIndex && lowIndex2 <= highIndex) {
            if (tmpArray[lowIndex1] <= tmpArray[lowIndex2]) {
                array[i] = tmpArray[lowIndex1];
                lowIndex1++;
            }
            else {
                array[i] = tmpArray[lowIndex2];
            }
            i++;
        }
        while (lowIndex1 <= midIndex) {
            array[i] = tmpArray[lowIndex1];
            i++;
            lowIndex1++;
        }
        while (lowIndex2 <= highIndex) {
            array[i] = tmpArray[lowIndex2];
            i++;
            lowIndex2++;
        }
        return Arrays.toString(array);
    }
}

MergeSortTest.java：

import java.util.Arrays;

import org.junit.Test;

public class MergeSortTest {

    int[] array = new int[] {6, 4, 10, 9, 3, 7, 2, 1};
    int[] sortedArray = new int[] {1, 2, 3, 4, 6, 7, 9, 10};
    int[] tmp = new int[array.length];

    @Test
    public void sort() {
        System.out.println("Unsorted array: " + Arrays.toString(array));
        String value = MergeSort.sort(array, tmp, 0, array.length - 1);
        assert(value == Arrays.toString(sortedArray));
        System.out.println("Sorted array: " + value);
    }
}

我可能做错了什么？

Answer 1

// Merge elements
        while(lowIndex <= midIndex && lowIndex2 <= highIndex) {
            if (tmpArray[lowIndex1] <= tmpArray[lowIndex2]) {
                array[i] = tmpArray[lowIndex1];
                lowIndex1++;
            }
            else {
                array[i] = tmpArray[lowIndex2];
            }
            i++;
        }

应该是

// Merge elements
        while(lowIndex <= midIndex && lowIndex2 <= highIndex) {
            if (tmpArray[lowIndex1] <= tmpArray[lowIndex2]) {
                array[i] = tmpArray[lowIndex1];
                lowIndex1++;
            }
            else {
                array[i] = tmpArray[lowIndex2];
                lowIndex2++; // add this one
            }
            i++;
        }

Answer 2

我发现您的合并排序实现存在四个问题。

首先，以下while循环中的条件不正确：

    // Merge elements
    while(lowIndex <= midIndex && lowIndex2 <= highIndex) {

您将在循环中递增lowIndex1，而不是lowIndex，因此该循环应如下所示：

    // Merge elements
    while(lowIndex1 <= midIndex && lowIndex2 <= highIndex) {

其次，正如@andy所指出的，您需要在while循环内的if语句的else子句中递增lowIndex2。

第三，使用变量i来跟踪将数组的两个排序的子部分合并后的排序值写回array的位置。sort方法对数组的一部分从lowIndex到highIndex进行排序，因此需要将i初始化为lowIndex，而不是0，以确保您的代码将合并后的元素写入array中的正确位置。

最后，如果highIndex等于lowIndex，会发生什么呢？在本例中，您将对数组的单个元素部分进行排序。按照原样，您的代码将把midIndex设置为0。代码的其余部分要求midIndex介于lowIndex和highIndex之间，如果lowIndex大于0，则不再为真。当然，您可以通过不执行任何操作来对1元素集合进行排序，因此在这种情况下，可以跳过合并。我建议在else子句中添加一条return语句：

   if (highIndex > lowIndex) {
        midIndex = (highIndex + lowIndex) / 2;
        sort(array, tmpArray, lowIndex, midIndex);
        sort(array, tmpArray, midIndex + 1, highIndex);
    } else {
        // Nothing to do, we only have one element to sort
        return Arrays.toString(array);
    }

我对您的代码进行了这四处更改，发现您的JUnit测试通过了。我还为其他数组编写了额外的测试，发现这些测试也通过了。