В Java
- Сортировка слиянием — это алгоритм сортировки
- Сортировка слиянием была создана Джоном фон Нейманом в 1945 году.
- Сортировка слиянием использует метод Разделяй и властвуй для сортировки элементов в массиве.
Разделяй и властвуй
- Разделяй и властвуй — подход к решению проблем
- Подход разделяй и властвуй
состоит из трех шагов. 1. Разделяй: разбей заданную проблему на подзадачи
2. Властвуй: решай подзадачи
3. Комбинируй: Правильно сочетайте ответы
Забавный факт: сортировка слиянием — классический пример для понимания подхода «разделяй и властвуй».
Приступаем к изучению сортировки слиянием
Во-первых, мы увидим работу сортировки слиянием.
Здесь красныйцвет означает –› разделяй
, а зеленыйцвет означает –› властвуй
Пошаговая разбивка алгоритма сортировки слиянием
1) Возьмем массив чисел
2) Теперь возьмите середину этого массива
Вот в этом случае
Размер этого массива равен 7.
таким образом, начальный и конечный индексы будут 0 и 6 (соответственно).
теперь, чтобы найти середину массива, есть простая формула : (l+r)/2.
здесь l — левая часть этого массива, которая является началом массива = 0.
и r — правая часть этого массива, равная = a.length-1 = 7–1 = 6.
середина = (l+r) / 2
середина = ( 0 + 6) / 2 = 3
элемент с индексом «3» равен 3
3) Разделите массив на левый и правый массивы
Разделите массив, пока не останется только 1 элемент слева в каждом массиве
означает l ‹ r
Если в массиве только 1 элемент, это означает, что массив отсортирован
Давайте посмотрим на деление массива в действии
Примечание: мы не берем значения с плавающей запятой в l, r и mid
Примечание: это индексы, на которые указывает l, r и mid.
Шаг 1:
l = 0
r = a.length-1 = 6
mid = (l+r)/2 = 3
Вот 2 массива «слева» и «справа».
Размер массива «left»: (mid-l)+1
(3–0) + 1 = 4
Размер массива право: (r-mid)
(6–3) = 3
влево[] = {28, 27, 43, 3}
вправо[] = {9, 82, 10}
Теперь, как описано в пункте (3) выше
«Разделите массив, пока в каждом массиве не останется только 1 элемент»
Шаг 2:
Теперь мы разделим массив «left»
l = 0
r = a.length-1 = 3
mid = (l+r)/2 = 1
Вот 2 массива «слева» и «справа».
Размер массива «left»: (mid-l)+1
(1–0) + 1 = 2
Размер массива «право»: (r-mid)
(3–1) = 2
влево[] = {38, 27}
вправо[] = {43, 3}
Шаг 3.
Теперь мы разделим массив «right»
l = 0
r = a.length-1 = 2
mid = (l+r)/2 = 1
Вот 2 массива «слева» и «справа».
Размер массива «left»: (mid-l)+1
(1–0) + 1 = 2
Размер массива «right»: (r-mid)
(2–1) = 1
влево[] = {9, 82}
вправо[] = {10}
Вот так мы разделили эти массивы на левый и правый
После деления окончательного разделенного массива это
Теперь пришло время объединить эти отсортированные массивы.
Как сортируются эти массивы?
Если массив содержит только один элемент, то очевидно, что все эти массивы отсортированы.
Слияние — это процесс объединения отсортированных массивов в один отсортированный массив. Здесь мы использовали средства двустороннего слияния, если есть 4 массива, то мы сортируем первые 2, затем вторые 2, затем сортируем результат обоих отсортированных массивов.
Хорошо, теперь давайте объединим эти отсортированные массивы
«Процесс слияния»
Найдите размер левого и правого массива
середина = (l + r) / 2
leftArraySize = (mid-l)+1
rightArraySize = (r-средний)
Возьмем указатели i& j на левый массив и правый массив соответственно.
возьмем указатель k = l(здесь l = левый массива) также для указания, где хранить следующий элемент в основном массиве (возьмем основной массив с именем a)
теперь проверьте
1) если влево[i] ‹ вправо[j], если да, то a[k] = влево[i]
2) затем увеличить k и i
3) иначе a[k] = право[j]
4) затем увеличить k и j
повторяйте эти 4 шага, пока
i ‹ размер левого массива && j ‹ размер правого массива
теперь что если это условие выполнено и цикл останавливается и все равно в массиве остались элементы, для этого скопируем оставшиеся элементы из массива(остались с элементами)
Ура! Объединение завершено.
Давайте посмотрим на слияние массива в действии.
Здесь у нас есть 2 массива
left = {38}
right = {27}
объединил их, используя описанный выше процесс
a[] = {27, 38}
Хорошо, давайте возьмем сложный пример и разберемся в нем
слева = {27, 38}
справа = {3, 43)
i = 0
j = 0
k = l
А пока забудь про k и a, ты поймешь это по коду
Шаг 1:
слева [i] = 27 и справа [j] = 3
влево[i] ‹ вправо[j] = ложь
вправо[j] ‹ влево[i] = верно
a[k] = right[j]
j++ и k++
a = {3}
Шаг 2:
слева [i] = 27 и справа [j] = 43
влево[i] ‹ вправо[j] = правда
вправо[j] ‹ влево[i] = ложь
a[k] = left[i]
i++ и k++
a = {3, 27}
Шаг 3.
слева [i] = 38 и справа [j] = 43
влево[i] ‹ вправо[j] = правда
вправо[j] ‹ влево[i] = ложь
a[k] = left[i]
i++ и k++
a = {3, 27, 38}
теперь мы дошли до конца обоих массивов
поэтому просто скопируйте все оставшиеся элементы из правого массива в основной массив a
a = {3, 27, 38, 43}
Так мы объединили все оставшиеся левый и правый массивы
и результат будет выглядеть так
Итак, концептуальная часть сортировки слиянием завершена.
Теперь вот код алгоритма сортировки слиянием.
Пример кода сортировки слиянием
Важные характеристики сортировки слиянием:
- Сортировка слиянием не является алгоритмом на месте: для выполнения сортировки требуются вспомогательные массивы.
- Временная сложность сортировки слиянием равна O(N log N) по основанию 2. Мы многократно делим массив пополам на этапе разделения.
- Сортировка слиянием полезна для сортировки связанных списков.
- Сортировка слиянием — это стабильная сортировка, которая означает, что один и тот же элемент в массиве сохраняет свои исходные позиции по отношению друг к другу.
- Пространственная сложность сортировки слиянием составляет O (n). Это означает, что этот алгоритм занимает много места и может замедлять работу с последними наборами данных.
Вот и все. Мы завершили алгоритм сортировки слиянием. Это очень важный алгоритм, который нужно изучить и освоить, начиная с собеседования и заканчивая перспективой конкурентного программирования. Хотя мы не напрягаемся, потому что теперь мы его изучили, но продолжайте его пересматривать, иначе вы забудете.
Спасибо, что прочитали эту статью 😃️
Написано
Кришной Вадхвани
