Блог

Главная - Вопросы по программированию - Использование вспомогательного метода при рекурсивной сортировке

Использование вспомогательного метода при рекурсивной сортировке

#java #arrays #sorting #generics #timsort

#java #массивы #сортировка #обобщения #timsort

Вопрос:

Я пытаюсь создать версию timSort на Java, которая использует вставку после массива.длина < 10, в противном случае используется сортировка слиянием. Предполагая, что мои вызовы InsertionSort и merge верны, что мешает следующему выполнить сортировку вставки и правильную временную сортировку?

 /**
 * timSort is a generic sorting method that sorts an array of Comparable data
 * using the TimSort algorithm. Make sure this method is public so that we can
 * test it.
 * 
 * @param data The array of data to be sorted
 * @param      <E> The Generic Element.
 */
public static <E extends Comparable<E>> void timSort(E[] data)
{
    timSortHelper(data, 0, data.length - 1);


}

/**
 * timSortHelper is a generic sorting method that sorts a sub-array array of
 * Comparable data using the TimSort algorithm. This method should be public for
 * testing purposes but would normally be private.
 * 
 * Ranges are specified with the parameters left and right, which are inclusive.
 * 
 * @param       <E> The Generic Element.
 * @param data  The array of data to sort
 * @param left  The index of the left-most position to sort
 * @param right The index of the right most position to sort
 */
public static <E extends Comparable<E>> void timSortHelper(E[] data, int left, int right)
{
    // General Case: The sublist has at least one item in it.

    if ((right - left) >= 1)
    {

        int middle1 = (left   right) / 2;
        int middle2 = middle1   1;
        if (data.length < 10)
        {
            insertionSort(data);
        }
        else
        {
            timSortHelper(data, left, middle1);
            timSortHelper(data, middle2, right);

        }
        merge(data, left, middle1, middle2, right);
    }
}

Комментарии:

1. Отладьте свою программу. Это, безусловно, самый простой способ выяснить, не видна ли проблема сразу.

2. отладчик показывает, что он выбирает правильные индексы, но data.length не передается рекурсивно как меньший диапазон. вот из-за чего у меня возникли проблемы с пониманием того, что рекурсивный вызов проходит в меньшем диапазоне подмассива, но при тестировании, чтобы увидеть, равна ли длина < 10, он ссылается на исходный массив

3. Похоже, что ваш метод работает именно так, как вы описываете, но вы сформулировали проблему иначе, чем, как я подозреваю, вы намеревались сделать. В частности, array.length не изменяется во время повторного использования — это всегда одно и то же свойство одного и того же объекта массива — так что либо ваш метод будет использовать сортировку по вставке сразу, либо он никогда не будет ее использовать. Если вы хотите переключиться на сортировку по вставке при работе с небольшими интервалами массива, то вы хотите проводить тестирование right - left .

4. Итак, второй оператор if вызывает ошибку?

Ответ №1:

Пришлось вызвать отдельную сортировку вставки, которая приняла дополнительные параметры для скорректированных индексов