Введение в сортировку слиянием в Java

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

Как работает сортировка слиянием?

Давайте рассмотрим несортированный массив, который необходимо отсортировать с помощью алгоритма сортировки слиянием. Вот шаги по сортировке массива со значениями: 18, 8, 4, 13, 10, 12, 7 и 11:

  • Первый шаг включает в себя поиск элемента pivot, на основе которого наш входной массив будет разделен на подмассивы.
  • Будем считать, что элемент 13 выбран в качестве стержня, поэтому исходный массив будет разделен на два подмассива. Первый вложенный массив будет содержать 18, 8, 4, 13, а второй вложенный массив будет содержать оставшиеся элементы 10, 12, 7, 11.
  • Подмассивы, полученные на шаге 2, далее подразделяются, как на шаге 1, и это продолжается.
  • Как только основной массив разделен на подмассивы с отдельными элементами, мы снова начинаем объединять эти подмассивы таким образом, чтобы объединенные элементы были в отсортированном порядке.
  • Вот как работает принцип «разделяй и властвуй»:

Программа для сортировки слиянием в Java

Вот пример кода, показывающий реализацию сортировки слиянием в Java:

Код:

package com.edubca.sorting;
public class MergeSort (
private int() array;
private int() tempMergedArr;
private int length;
public static void main(String a())(
int() inputArr = (18, 8, 4, 13, 10, 12, 7, 11);
MergeSort mergeSort = new MergeSort();
mergeSort.sort(inputArr);
for(int i:inputArr)(
System.out.print(i + " ");
)
)
public void sort(int inputArr()) (
this.array = inputArr;
this.length = inputArr.length;
this.tempMergedArr = new int(length);
performMergeSort(0, length - 1);
)
private void performMergeSort(int lowerIndex, int higherIndex) (
if (lowerIndex < higherIndex) (
int middle = lowerIndex + (higherIndex - lowerIndex) / 2;
// Sort the left side of the array call performMergeSort recursively
performMergeSort(lowerIndex, middle);
// Sort the right side of the array call performMergeSort recursively
performMergeSort(middle + 1, higherIndex);
// Merge subparts using a temporary array
mergeData(lowerIndex, middle, higherIndex);
)
)
private void mergeData (int lowerIndex, int middle, int higherIndex) (
for (int i = lowerIndex; i <= higherIndex; i++) (
tempMergedArr(i) = array(i);
)
int i = lowerIndex;
int j = middle + 1;
int k = lowerIndex;
while (i <= middle && j <= higherIndex) (
if (tempMergedArr(i) <= tempMergedArr(j)) (
array(k) = tempMergedArr(i);
i++;
) else (
array(k) = tempMergedArr(j);
j++;
)
k++;
)
while (i <= middle) (
array(k) = tempMergedArr(i);
k++;
i++;
)
)
)

Приведенный выше код будет производить отсортированный массив в качестве вывода.

Выход:

Когда мы должны использовать сортировку слиянием?

Сортировка слиянием может использоваться в следующих сценариях:

  • Если сортируемая структура данных не поддерживает произвольный доступ, сортировка слиянием может быть полезной и эффективной.
  • Когда требуется высокий уровень параллелизма, можно использовать сортировку слиянием, поскольку различные подзадачи могут быть решены независимо с использованием нескольких процессов, работающих параллельно.
  • Сортировка слиянием выполняется быстрее при работе со связанными списками, поскольку указатели могут быть легко изменены при объединении списков.
  • Сортировка слиянием может рассматриваться как стабильная сортировка, что означает, что один и тот же элемент в массиве сохраняет свои исходные позиции относительно друг друга. В случаях, когда требуется высокая стабильность, можно перейти к сортировке слиянием.

Анализ сложности сортировки слиянием

Ниже анализируется сложность сортировки слиянием:

  • Сортировка слиянием является рекурсивным алгоритмом, и его сложность по времени составляет O (n * log n) во всех трех случаях (наихудший, лучший и средний), поскольку сортировка слиянием разделяет массив на две равные половины и требует для их объединения линейного времени.
  • Пространственная сложность сортировки слиянием - O (n), поскольку она работает на рекурсивном подходе. Следовательно, сортировку слиянием можно считать быстрым, экономичным по времени и времени алгоритмом.

Сравнение сортировки слиянием с другими алгоритмами

Ниже приведено сравнение сортировки слиянием с другими алгоритмами:

  • Сортировка кучи имеет ту же сложность по времени, что и сортировка слиянием, но требует только O (1) вспомогательного пространства вместо O (n) сортировки слиянием. Следовательно, сортировка кучи более экономична, чем сортировка слиянием.
  • Реализации быстрой сортировки обычно превосходят сортировку слиянием для сортировки массивов на основе ОЗУ.
  • Сортировка слиянием превосходит алгоритмы быстрой сортировки и сортировки кучи при работе со связанным списком, поскольку указатели могут быть легко изменены.

Заключение-Программа для сортировки слиянием в Java

Из статьи делается вывод, что сортировка слиянием является важным понятием, которое нужно понимать, когда дело доходит до алгоритмов.

Рекомендуемые статьи

Это руководство к Программе сортировки слиянием на Java. Здесь мы обсуждаем, как следует работать, его использование, программу сортировки слиянием и т. Д. Вы также можете просмотреть другие наши статьи, чтобы узнать больше-

  1. Слияние сортировки в Java
  2. Алгоритмы сортировки слиянием в Java
  3. Сортировка кучи в C
  4. Сортировка кучи в Java
  5. Инструменты развертывания Java
  6. Сортировка кучи в Python
  7. Алгоритмы быстрой сортировки в Java
  8. Топ 6 Алгоритм сортировки в JavaScript
  9. 6 лучших алгоритмов сортировки в Python

Категория:

Разработка программного обеспечения