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

1. Введение

В этом руководстве мы рассмотрим алгоритм сортировки слиянием и его реализацию на Java .

Сортировка слиянием - один из наиболее эффективных методов сортировки, основанный на парадигме «разделяй и властвуй».

2. Алгоритм

Сортировка слиянием - это алгоритм «разделяй и властвуй», в котором мы сначала разделяем проблему на подзадачи. Когда решения для подзадач готовы, мы объединяем их вместе, чтобы получить окончательное решение проблемы.

Это один из алгоритмов, который можно легко реализовать с помощью рекурсии, поскольку мы имеем дело с подзадачами, а не с основной проблемой.

Алгоритм можно описать как следующий двухэтапный процесс:

  • Разделить: на этом этапе мы делим входной массив на 2 половины , при этом точка поворота является средней точкой массива. Этот шаг выполняется рекурсивно для всех половинных массивов до тех пор, пока не останется больше половинных массивов для разделения.
  • Conquer: на этом этапе мы сортируем и объединяем разделенные массивы снизу вверх и получаем отсортированный массив.

На следующей диаграмме показан полный процесс сортировки слиянием для примера массива {10, 6, 8, 5, 7, 3, 4}.

Если мы внимательно рассмотрим диаграмму, то увидим, что массив рекурсивно делится на две половины, пока размер не станет равным 1. Когда размер станет равным 1, процессы слияния вступят в действие и начнут объединять массивы обратно во время сортировки:

3. Реализация

Для реализации мы напишем функцию mergeSort, которая принимает входной массив и его длину в качестве параметров. Это будет рекурсивная функция, поэтому нам нужны базовые и рекурсивные условия.

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

Для рекурсивного случая мы получаем средний индекс и создаем два временных массива l [] и r [] . Затем функция mergeSort вызывается рекурсивно для обоих подмассивов :

public static void mergeSort(int[] a, int n) { if (n < 2) { return; } int mid = n / 2; int[] l = new int[mid]; int[] r = new int[n - mid]; for (int i = 0; i < mid; i++) { l[i] = a[i]; } for (int i = mid; i < n; i++) { r[i - mid] = a[i]; } mergeSort(l, mid); mergeSort(r, n - mid); merge(a, l, r, mid, n - mid); }

Затем мы вызываем функцию слияния, которая принимает входные данные и подмассивы, а также начальный и конечный индексы обоих подмассивов .

Функция слияния сравнивает элементы обоих подмассивов один за другим и помещает меньший элемент во входной массив.

Когда мы достигаем конца одного из подмассивов, остальные элементы из другого массива копируются во входной массив, тем самым давая нам окончательный отсортированный массив:

public static void merge( int[] a, int[] l, int[] r, int left, int right) { int i = 0, j = 0, k = 0; while (i < left && j < right) { if (l[i] <= r[j]) { a[k++] = l[i++]; } else { a[k++] = r[j++]; } } while (i < left) { a[k++] = l[i++]; } while (j < right) { a[k++] = r[j++]; } } 

Модульный тест для программы:

@Test public void positiveTest() { int[] actual = { 5, 1, 6, 2, 3, 4 }; int[] expected = { 1, 2, 3, 4, 5, 6 }; MergeSort.mergeSort(actual, actual.length); assertArrayEquals(expected, actual); }

4. Сложность

Поскольку сортировка слиянием является рекурсивным алгоритмом, временная сложность может быть выражена следующим рекурсивным соотношением:

T(n) = 2T(n/2) + O(n)

2T (n / 2) соответствует времени, необходимому для сортировки подмассивов, и времени O (n) для объединения всего массива.

После решения сложность времени составит O (nLogn).

Это верно для худшего, среднего и лучшего случая, поскольку он всегда делит массив на два, а затем объединяется.

Пространственная сложность алгоритма составляет O (n), поскольку мы создаем временные массивы при каждом рекурсивном вызове.

5. Заключение

В этом кратком руководстве мы увидели работу алгоритма сортировки слиянием и то, как мы можем реализовать его на Java.

Весь рабочий код доступен на GitHub.