Сортировка слиянием - это алгоритм сортировки, который использует парадигму «разделяй и властвуй» для сортировки заданного массива. Сортировка слиянием эффективна и имеет временную сложность O (n logn), что хорошо для алгоритма сортировки и работает намного лучше по сравнению с алгоритмами сортировки, особенно с пузырьковой сортировкой.
Простые шаги для реализации алгоритма сортировки слиянием
- Напишите функцию слияния массивов: функция слияния в основном объединяет 2 массива в один, подробнее см. Https://uzochukwubenamara.medium.com/javascript-how-to-merge-2-arrays-f69415434ca9.
Вышеупомянутая функция в основном объединяет 2 отдельных массива в один, используя хэш-таблицу, в которой хранятся индексы массивов внутри нее на основе условия цикла while. I = 0 и j = 0 просто указывают циклу массива, где начать, скажем, с 1 для i и 12 для j. Затем запускается цикл while на основе условия, обеспечивающего правильное хранение массивов в хеш-таблице.
2. Написание функции MergeSort: Теперь, когда у нас есть функция, которая просто объединяет 2 массива, мы можем приступить к написанию функции mergeSort.
Примечание. Это сильно зависит от R ecursion (, функции, которая продолжает вызывать себя до тех пор, пока не будет выполнено условие ). Если базовый вариант не определен, последует бесконечный цикл.
Наша функция mergeSort будет иметь свой базовый случай как 1, что означает, что если длина нашего массива равна 1, рекурсивная функция mergeSort должна остановиться и, следовательно, вернуть отсортированный массив. .
Как видно выше, мы разделяем наш массив на по середине, справа и слева , который представляет собой шаблон Разделяй и властвуй, в котором массив разделен на 3 части, над которыми затем можно будет работать. Это повышает эффективность и сокращает время O (nlogn), поскольку количество операций было разбито на.
O (logn): количество разложений - это сколько раз нам нужно разбить массив, чтобы получить один элемент? т.е. 3 в нашем случае, то есть 1. [23,345,89, 45, 22] → 2. [23, 345], [89], [45,22] → 3. [23], [345], [89], [45], [22]
O (n): сравнения на разложение
O (logn) + O (n) = O (n logn)
Затем в приведенной выше функции mergeSort () мы вызываем функцию mergeSort () для правого и левого массивов. рекурсивно, чтобы расположить меньшее значение массива слева, а большее - вправо, пока значения не будут отсортированы надлежащим образом. После сортировки их нужно объединить в один большой массив. Для этого мы бы использовали нашу предыдущую функцию arrayMerge (), чтобы добиться этого, поскольку все, что она делает, - это объединение отдельных массивов.
Итак, алгоритм сортировки слиянием стал проще! Надеюсь, вам понравилось это чтение. Спасибо.
