Может кто-нибудь помочь понять алгоритм сортировки слиянием? - PullRequest
Новая
       17

Может кто-нибудь помочь понять алгоритм сортировки слиянием?

0 голосов
/ 23 апреля 2019

Мой вопрос: в методе mergeSort мы погружаем массив в меньшие и меньшие массивы с помощью рекурсии, однако я не могу понять, как они хранятся и как мы вводим все эти массивы в метод сортировки, когда он не является рекурсивным? Например, допустим, у нас есть числа 2, 1, 5, 8, 9 в массиве. После этого у нас будет 5 массивов, каждый с одним элементом. Итак, теперь мы должны объединить все из них, но как выполняются шаги, что мы вводим, чтобы получить два отсортированных массива: 1, 2 и 5, 8, 9, которые объединятся, чтобы дать 1, 2, 5, 8, 9? 

public class main {

    // Helper method to print out the integer array.
    private static void printArray(int[] array) {
        for (int i: array) {
            System.out.print(i + " ");
        }
        System.out.println();
    }

    // Breaks down the array to single or null elements in array.
    private static int [] mergeSort(int[] array) {
        // Recursive control 'if' statement.
        if (array.length <= 1) {
            return array;
        }
        int midpoint = array.length / 2;
        // Declare and initialize left and right arrays.
        int[] left = new int[midpoint];
        int[] right;
        if (array.length % 2 == 0) { // if array.length is an even number.
            right = new int[midpoint];
        } else {
            right = new int[midpoint + 1];
        }

        // Populate the left and right arrays.
        for (int i = 0; i < midpoint; i++) {
            left[i] = array[i];
        }

        for (int j = 0; j < right.length; j++) {
            right[j] = array[midpoint+j];
        }

        int[] result = new int[array.length];

        // Recursive call for left and right arrays.
        left = mergeSort(left);
        right = mergeSort(right);

        // Get the merged left and right arrays.
        result = merge(left, right);

        // Return the sorted merged array.
        return result;
    }

    // Merges the left and right array in ascending order.

    private static int[] merge(int[] left, int[] right) {
        // Merged result array.

        int[] result = new int[left.length + right.length];

        // Declare and initialize pointers for all arrays.
        int leftPointer, rightPointer, resultPointer;
        leftPointer = rightPointer = resultPointer = 0;

        // While there are items in either array...

        while(leftPointer < left.length || rightPointer < right.length) {

            // If there are items in BOTH arrays...

            if (leftPointer < left.length && rightPointer < right.length) {

                // If left item is less than right item...

                if (left[leftPointer] < right[rightPointer]) {

                    result[resultPointer++] = left[leftPointer++];

                } else {

                    result[resultPointer++] = right[rightPointer++];
                }
            }

            // If there are only items in the left array...

            else if (leftPointer < left.length) {

                result[resultPointer++] = left[leftPointer++];
            }
            // If there are only items in the right array...

            else if (rightPointer < right.length) {
                result[resultPointer++] = right[rightPointer++];
            }
        }
        return result;
    }

    public static void main(String args[]) {
        // Initial array with print out.

        int[] array = { 2, 1, 5, 8, 9 };

        System.out.println("Initial Array: ");

        printArray(array);

        // Sorted and merged array with print out.

        array = mergeSort(array);

        System.out.println("Sorted Array: ");

        printArray(array);
    }
}

1 Ответ

0 голосов
/ 23 апреля 2019

В приведенном примере кода есть утечка памяти, он переназначается влево и вправо с результатом mergeSort, теряя то, что было выделено слева и справа до рекурсивных вызовов mergeSort.

В вопросе упоминается нерекурсивная сортировка, которая была бы сортировкой по принципу снизу вверх. Большинство реализаций библиотек для стабильных сортировок представляют собой разновидность сортировки по принципу «снизу вверх», такую ​​как гибрид сортировки с вставкой и сортировки «снизу вверх». Ссылка на статью вики для базовой логики сортировки по принципу «снизу вверх»:

https://en.wikipedia.org/wiki/Merge_sort#Bottom-up_implementation

Чтобы объяснить сортировку по принципу «снизу вверх», массив из n элементов рассматривается как n прогонов размера 1, где прогон размера 1 можно считать отсортированным. Затем пары прогонов размера 1 объединяются для создания отсортированных прогонов размера 2. Пары отсортированных прогонов размера 2 объединяются для создания отсортированных прогонов размера 4 и т. Д., Пока объединение не произведет один отсортированный прогон. Нисходящий процесс аналогичен, за исключением того, что он рекурсивно разделяет массив (обычно путем генерации пар индексов для начала и конца прогонов), пока он не произведет два прогона размером 1, тогда и только тогда начинается процесс слияния, после которого он следует стек в некоторой степени похож на дерево, сначала глубина, а потом слева.

Используя пример массива, но переупорядоченный, 2 1 9 8 5, снизу вверх будет выглядеть так 

|2 1 9 8 5|
|2|1|9|8|5|       split
|1 2|             merge
    |8 9|         merge
        |5|       copy
|1 2 8 9|         merge
        |5|       copy
|1 2 5 8 9|       merge

Для сверху вниз: 

|2 1 9 8 5|
|2 1 9|8 5|       split
|2 1|9|           split
|2|1|             split
|1 2|             merge
|1 2 9|           merge
      |8|5|       split
      |5 8|       merge
|1 2 5 8 9|       merge
...