Сортировка слиянием выдает ошибку ArrayOutOfBounds в шаге копирования поверх? - PullRequest
Новая
       23

Сортировка слиянием выдает ошибку ArrayOutOfBounds в шаге копирования поверх?

0 голосов
/ 14 декабря 2018

Я пытаюсь реализовать универсальный алгоритм сортировки слиянием, который использует временный массив для хранения объединенных частей, а затем копирует отсортированные данные.Однако программа продолжает сбой в шаге копирования (последний цикл 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++];
    }
}

Ответы [ 2 ]

0 голосов
/ 14 декабря 2018

У вас должно быть 2 временных массива: просто взгляните на Реализация алгоритма слияния-сортировки

0 голосов
/ 14 декабря 2018 
array[newIndex++] = temp[newIndex++];

Вы увеличиваете newIndex в этой строке дважды.Разделите это на две строки кода, одну для приращения, затем одну для использования в качестве индекса массива.

Примечание: Этот шаблон работает в других местах вашего кода, потому что вы увеличиваетедва разных индекса.Например. 

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

В последнем цикле он выходит за пределы диапазона из-за двойного приращения той же переменной при достижении конца ваших массивов.

...