java - 合并排序在复制步骤中抛出 ArrayOutOfBounds 错误？

Question

我正在尝试实现一个通用的合并排序算法，该算法使用临时数组来存储合并的部分，然后复制排序的数据。但是，程序在复制步骤(最后一个 while 循环)中不断失败，并抛出 ArrayIndexOutOfBounds 异常。我很困惑为什么会发生这种情况!

我知道在这个程序中使用 Array.copy 更简单，但我正在尝试使用循环进行练习。

public static <E extends Comparable<E>> void mergeSort2(E[] array) {
    mergeSortHelper2(array, 0, array.length - 1);
}

private static <E extends Comparable<E>> void mergeSortHelper2(E[] array, int firstIndex, int lastIndex) {
    if (firstIndex >= lastIndex) {
        return;
    }
    //otherwise divide
    int middle = (firstIndex + lastIndex) / 2;

    //conquer with recursion
    mergeSortHelper2(array, firstIndex, middle);
    mergeSortHelper2(array, middle + 1, lastIndex);

    //combine: take in the original array, and all indices
    merge2(array, firstIndex, middle, middle + 1, lastIndex);
}

private static <E extends Comparable<E>> void merge2(E[] array, int leftFirst, int leftLast, int rightFirst, int rightLast) {
    E[] temp = (E[]) Array.newInstance(array.getClass().getComponentType(), (rightLast - leftFirst + 1));
    int indexLeft = leftFirst;
    int indexRight = rightFirst;
    int index = 0;

    while (indexLeft <= leftLast && indexRight <= rightLast) {
        if (array[indexLeft].compareTo(array[indexRight]) < 0) {
            temp[index++] = array[indexLeft++];
        }
        else {
            temp[index++] = array[indexRight++];
        }
    }

    while (indexLeft <= leftLast) {
        temp[index++] = array[indexLeft++];
    }
    while (indexRight <= rightLast) {
        temp[index++] = array[indexRight++];
    }

    int newIndex = 0;

    while (newIndex != temp.length - 1) {
        array[newIndex++] = temp[newIndex++];
    }
}

Answer 1

array[newIndex++] = temp[newIndex++];

您在该行上将 newIndex 递增两次。将其分成两行代码，一行用于递增，然后一行将其用作数组索引。

注意:此模式适用于代码中的其他位置，因为您要递增两个不同索引。例如。

temp[index++] = array[indexLeft++];

由于到达数组末尾时同一变量的双倍增量，它在最终循环中超出了范围。