Объединить Сортировать в JavaScript - Различные типы недвижимости | Разработка программного обеспечения 2025

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

Алгоритмы сортировки очень важны в информатике. Результатом сортировки является упорядочение элементов списка в определенном порядке (по возрастанию или по убыванию). Сортировка слиянием в JavaScript является одним из наиболее эффективных алгоритмов сортировки, поскольку она основана на концепции разделяй и властвуй. Как следует из названия, сначала разделите большую проблему на маленькие проблемы, чем решайте меньшие проблемы, чтобы решить большую проблему. Концептуально сортировка слиянием представляет собой комбинацию двух основных алгоритмов, называемых MERGE и MERGE_SORT.

который работает следующим образом:

Разделите несортированный список на n номеров одноэлементных подсписков (n - общее количество элементов в несортированном списке).
Повторно объединяйте подсписки в отсортированные подсписки, пока не будет только один отсортированный список.

Реализация сортировки слиянием в JavaScript

Алгоритм MERGE следует процедуре объединения двух отсортированных списков в один отсортированный список.

Пример: предположим, что есть два списка, то есть Список 1 (1, 5, 3) и Список 2 (7, 2, 9).

1. Сначала отсортируйте оба списка.

Теперь мы увидим и применим технику Е на нем.

2. Затем мы создадим новый список размером x + y, где x - количество элементов в списке 1, а y - количество элементов в списке 2.

В нашем случае x = 3 и y = 3, поэтому x + y = 6.

3. Теперь у нас есть два указателя.
Первый указатель, указывающий на первую позицию списка 1, и второй указатель, указывающий на первую позицию списка 2.

4. Затем мы сравним значение обоих указателей. Указатель с меньшим значением, скопируйте этот элемент в Список 3 и переместите указатель вправо от списка с меньшим значением и результирующего списка (т.е. Список 1 и Список 3)

5. Аналогично, повторите шаг 4 снова и снова.

Дальнейшее прохождение …

Примечание . Если один из списков (т.е. список 1 или список 2) полностью пройден, как в случае, скопируйте все содержимое другого списка из указателя в список результатов (т.е. список 3) следующим образом.

ПСЕВДОКОД

Function merge (sublist1, sublist2) ( Create var for result list While sublist1 length > 0 and sublist2 length > 0 If sublist1(0) < sublist2(0) Copy the sublist1 pointer value to result list and Shift pointer of sublist1 to right else Copy the sublist2 pointer value to result list and Shift pointer of sublist2 to right Return concat sublist1 or sublist2 (depending if node1 is empty or not)

Алгоритм MERGE_SORT делит данный несортированный список на минимальный размер, а затем вызывает алгоритм MERGE для объединения списка в новый отсортированный список.

ПСЕВДОКОД

function mergeSort(list) ( If list length < 2 Return list Create var for middle index of list Create var for left index of list Create var for right index of list Recursively call mergeSort function )

пример

Здесь мы следуем нисходящей реализации Merge Sort. Он начинается сверху и продолжается вниз, при этом каждый рекурсивный ход задает один и тот же вопрос «Что нужно сделать, чтобы отсортировать список?», А ответ на этот вопрос звучит так: «Разбить список на две части, сделать рекурсивный вызов и объединить Результаты".

Код в JavaScript

// Split the list into halves and merge them recursively function mergeSort (list) ( if (list.length < 2) ( return list;// return once we hit a list with a single element ) var mid = Math.floor(list.length / 2); var left = mergeSort(list.slice(0, mid)); var right = mergeSort(list.slice(mid)); return merge(left, right); ) // compare the lists element by element and return the concatenated resultList function merge (sublist1, sublist2) ( var resultList = (); while (sublist1.length > 0 && sublist2.length > 0) resultList.push(sublist1(0) < sublist2(0)? sublist1.shift() : sublist2.shift()); return resultList.concat(sublist1.length? sublist1 : sublist2); ) const list = (6, 5, 3, 1, 8, 7, 2, 4, 2, 5, 1, 2, 3) console.log(mergeSort(list)) //( 1, 1, 2, 2, 2, 3, 3, 4, 5, 5, 6, 7, 8 )

Основная функция сортировки слиянием будет разделять данный список на меньшие списки на каждой итерации рекурсивного вызова. Не забывайте, что рекурсия требует базового условия, чтобы избежать бесконечной рекурсии. В нашем случае мы имеем:

if (list.length < 2) ( return list;// return once we hit a list with a single element )

После того, как мы настроили базовое условие для рекурсии, мы определим средний индекс, чтобы разделить данный список на левый и правый подсписки, как вы можете видеть выше на диаграмме примера. Затем нам нужно объединить левый подсписок и правый подсписок, который мы сейчас рассмотрим. В приведенной выше функции слияния нам нужно убедиться, что мы сортируем все элементы в левом подсписке и правом подсписке. список. Мы сделаем это с помощью цикла while. В цикле while мы будем сравнивать элемент в левом подсписке и элемент в правом подсписке один за другим. Мы можем вставить меньшее из двух значений в список результатов и соответственно переместить курсор левого подсписка и правого подсписка. Наконец, нам нужно объединить список результатов. Это очень важно! Если мы не сделаем этот последний шаг здесь, у нас будет неполный список элементов в конце, потому что условие цикла while будет не выполнено, как только один из двух указателей достигнет конца.

Выход:

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

Сортировка слиянием является стабильной, поскольку один и тот же элемент в массиве сохраняет свои исходные позиции относительно друг друга.
Сортировка слиянием не «на месте», так как во время слияния создается копия всего списка сортируется. Вследствие этого сложность пространства (O (n)) этого алгоритма фактически больше, чем у других, и его не следует использовать в сложных задачах, где пространство является премиальным.
Общая временная сложность сортировки слиянием составляет O (nLogn). Это более эффективно, так как в худшем случае время выполнения равно O (nlogn).

Вывод

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