Всем привет. В этой статье я постараюсь изо всех сил провести вас через реализацию (на JavaScript) одного из первых алгоритмов сортировки, которые я изучил как разработчик программного обеспечения, и объяснить его важность.
Зачем нужна сортировка слиянием?
Сортировка слиянием - это эффективный алгоритм сортировки, основанный на сравнении, в котором используется концепция «разделяй и властвуй». Это означает, что он будет непрерывно делить неупорядоченный список на более мелкие подсписки, пока не будет изолирован каждый элемент массива, затем сравнит каждый элемент списка и объединит массивы вместе по порядку.
Временная сложность сортировки слиянием составляет O (n * Log n) во всех трех случаях (худшем, среднем и лучшем), поскольку сортировка слиянием всегда делит массив на две половины и для объединения двух половин требуется линейное время. Для него требуется такое же количество дополнительного места, как и для несортированного массива. Если вы не знакомы со сложностями вычисления времени, вот хорошее введение, которое может помочь. Это делает сортировку слиянием одним из наиболее эффективных алгоритмов сортировки. Вы также можете обратиться к разделам Пузырьковая сортировка и Быстрая сортировка.
Пример
Прежде чем мы начнем кодировать это, давайте придумаем пример проблемы и визуализируем, как функция может работать. Возьмем пример массива [6, 5, 3, 1, 8, 7, 2, 4]. Теперь давайте посмотрим, как именно эта стратегия «разделяй и властвуй» будет выглядеть на диаграмме.
Обратите внимание, что мы непрерывно разбиваем наш массив на подмассивы, пока не изолировали каждый элемент. Затем мы объединяем каждый массив в более крупные массивы, сравнивая их, чтобы мы знали, как их расположить (через секунду мы увидим, как их сравнивать).
Реализация
Мы собираемся разбить эту функцию сортировки слиянием на три части, одну основную функцию, которая будет нашей функцией сортировки слиянием, а также две вспомогательные функции разделения и слияния, которые будут обрабатывать именно это.
Разделить
Это наша вспомогательная функция разделения, которую мы будем вызывать рекурсивно в нашей основной функции сортировки слиянием. Он будет непрерывно разбивать наши массивы на более мелкие подмассивы, пока каждый массив не будет иметь длину 1. Получение средней точки каждого массива позволяет нам разделить массив на две половины. Обратите внимание, что мы также учитываем случаи, когда наш массив может иметь нечетное количество элементов, используя метод Math.floor (). Этот метод возвращает наибольшее целое число, меньшее или равное заданному числу. Затем мы можем использовать эту среднюю точку в качестве индекса, чтобы сообщить нашей функции, где разделить или разрезать наш массив пополам.
Если мы возьмем массив [1, 4, 3, 6, 8] и передадим его в нашу функцию разделения, он должен вернуть [1, 4] [3, 6, 8].
Объединить
Это наша вспомогательная функция, которую мы будем использовать для рекурсивной сортировки и объединения наших массивов в один окончательный отсортированный массив. Эта функция примет в качестве аргументов два объединяемых массива. Чтобы успешно отсортировать и объединить эти два массива, нам нужно отслеживать, где мы находимся, когда мы проходим через каждый массив. Вот здесь и пригодятся наши указатели «i» и «j».
В этом случае мы используем цикл while для одновременного обхода обоих массивов. Наш базовый случай для нашего цикла - когда один из наших указателей (i или j) становится не меньше длины массива, через который они проходят, мы выйдем из нашего цикла while.
Мы сохраняем текущий элемент нашего первого массива как element1 и текущий элемент нашего второго массива как element2. Теперь все, что нам нужно сделать, это сравнить оба текущих элемента, вставить меньший элемент в наш результирующий массив и увеличить их указатель, чтобы мы не повторяли никаких элементов. Как только мы исчерпали хотя бы один массив, мы знаем, что остальные элементы в оставшемся массиве уже упорядочены, поэтому все, что нам нужно сделать, это вставить их в наш массив результатов. Мы не знаем, какой массив будет исчерпан первым, поэтому мы решаем этот пограничный случай, просматривая каждый массив и вставляя оставшиеся элементы в наш массив результатов.
MergeSort
Вот наша основная функция сортировки слиянием. Давайте разберемся, что происходит в приведенном выше коде. Наш базовый случай говорит нам, что если есть массив длины, он уже отсортирован. Затем мы вызываем нашу вспомогательную функцию разделения, которая отвечает за разбиение нашего массива на отдельные элементы. Мы сохраняем результат нашей функции разделения в нашей переменной массива разделения, которая позволяет нам получить доступ к обоим подмассивам по их индексам 0 и 1. Затем мы рекурсивно вызываем нашу функцию mergeSort для каждой половины переданного массива, чтобы убедиться, что мы продолжаем разбивать оба массива. Это сначала будет рекурсивно разделить нашу первую половину, чем рекурсивно вторую половину. Наконец, мы вызываем нашу функцию слияния, чтобы объединить отсортированные половинки вместе.
Ну вот и все, ребята!
Спасибо всем за чтение, и я надеюсь, что это помогло вам понять магию сортировки слиянием. До следующего раза .. удачного кодирования!
