Алгоритм слияния
Алгоритмы слияния — это семейство алгоритмов , которые принимают несколько отсортированных списков в качестве входных данных и создают на выходе один список, содержащий все элементы входных списков в отсортированном порядке. Эти алгоритмы используются в качестве подпрограмм в различных алгоритмах сортировки , наиболее известным из которых является сортировка слиянием .
Алгоритм слияния играет критическую роль в алгоритме сортировки слиянием , алгоритме сортировки на основе сравнения . Концептуально алгоритм сортировки слиянием состоит из двух шагов:
Пример сортировки слиянием приведен на иллюстрации. Он начинается с несортированного массива из 7 целых чисел. Массив разбит на 7 разделов; каждый раздел содержит 1 элемент и отсортирован. Затем отсортированные разделы объединяются для создания более крупных отсортированных разделов, пока не останется 1 раздел, отсортированный массив.
Объединение двух отсортированных списков в один может быть выполнено за линейное время и линейное или постоянное пространство (в зависимости от модели доступа к данным). Следующий псевдокод демонстрирует алгоритм, который объединяет входные списки (либо связанные списки , либо массивы ) A и B в новый список C. [1] [2] : 104 Функция head возвращает первый элемент списка; «удаление» элемента означает удаление его из списка, обычно путем увеличения указателя или индекса.
Когда входные данные представляют собой связанные списки, этот алгоритм может быть реализован для использования только постоянного объема рабочего пространства; указатели в узлах списков можно повторно использовать для учета и построения окончательного объединенного списка.
В алгоритме сортировки слиянием эта подпрограмма обычно используется для слияния двух подмассивов A[lo..mid] , A[mid+1..hi] одного массива A . Это можно сделать, скопировав подмассивы во временный массив, а затем применив описанный выше алгоритм слияния. [1] Выделения временного массива можно избежать, но за счет скорости и простоты программирования. Были разработаны различные алгоритмы слияния на месте, [3] иногда жертвуя ограничением линейного времени для создания алгоритма O ( n log n ) ; [4] см. Сортировка слиянием § Варианты для обсуждения.
