Алгоритм сортировки слиянием в Java

Сортировка слиянием – это алгоритм “разделяй и властвуй”, поскольку алгоритм разбивает исходный массив на более мелкие логические разделы. Алгоритм может быть реализован с использованием циклов или рекурсий. Две различные фазы – это фаза разделения и, во-вторых, фаза слияния.

Фаза разделения : Разделите массив на два несортированных массива. Каждый из разделенных массивов непрерывно разбивается на меньшие массивы до тех пор, пока не останется только несколько одноэлементных массивов. Одноэлементные массивы сортируются так, как в них содержится только один элемент.

Фаза слияния : Каждый из одноэлементных массивов теперь объединяется обратно в больший массив. На этапе слияния два массива объединяются таким образом, что элементы сортируются в новом более крупном отсортированном массиве. Этот процесс повторяется до тех пор, пока не останется один отсортированный массив. Это не алгоритм на месте, так как используются временные массивы.

Классификация алгоритмов

Следующая таблица содержит информацию об анализе алгоритма сортировки слиянием. Он определяет наихудший, средний и наилучший случаи с точки зрения временной сложности, а также наихудший случай с точки зрения пространственной сложности.

Пожалуйста, используйте следующую ссылку для объяснения обозначения Big-O и того, что такое хорошо, справедливо и плохо.

Сортировка слиянием На языке Java

public final class MergeSort {

    public void sort(int[] collection) {
        if (collection != null) {
            mergeSort(collection, 0 , collection.length);
        } else {
            throw new IllegalArgumentException("Input paramenter for array to sort is null.");
        }
    }

    public  void mergeSort(int[] collection, int minIndex, int maxIndex) {
        if (maxIndex - minIndex < 2) {
            return;
        }

        int centre = (minIndex + maxIndex) / 2;
        mergeSort(collection, minIndex, centre);
        mergeSort(collection, centre, maxIndex);
        mergeBack(collection, minIndex, centre, maxIndex);       
    }

    public void mergeBack(int[] collection, int minIndex, int centre, int maxIndex) {
        if (collection[centre - 1] <= collection[centre]) {
            return;
        }
        int tempMinIndex = minIndex;
        int tempCentre = centre;

        int tempIndex = 0;
        int[] tempArray = new int[maxIndex - minIndex];

        while ((tempMinIndex < centre) && (tempCentre < maxIndex)) {
            if(collection[tempMinIndex] <= collection[tempCentre]) {
                tempArray[tempIndex++] = collection[tempMinIndex++];    
            } else {
                tempArray[tempIndex++] = collection[tempCentre++];
            }
        }

        System.arraycopy(collection, tempMinIndex, collection, minIndex + tempIndex, centre - tempMinIndex);
        System.arraycopy(tempArray, 0, collection, minIndex, tempIndex);
    }   
}

Пример кода (GitHub)

Подробную информацию о классе MergeSort можно посмотреть здесь. Подробную информацию о тестовом классе JUnit для сортировки слиянием можно посмотреть здесь.

Вывод

Алгоритм сортировки слиянием является частью более крупной группы алгоритмов сортировки. Обучение на основе опыта – вот причина, по которой я создал этот пост о реализации алгоритма сортировки слиянием в Java. Я многое узнал о том, как другие решали алгоритм сортировки слиянием на других языках, включая различные реализации в Java.

Сообщение Алгоритм сортировки слиянием в Java появилось впервые на Code 2 Bits .

Оригинал: “https://dev.to/code2bits/merge-sort-algorithm-in-java-5gfd”