|
Персональные инструменты |
![]() |
||
|
![]() |
![]() Сортировка слияниемМатериал из CustisWikiВерсия от 20:16, 17 октября 2005; BenderBot (обсуждение | вклад) (реплицировано из внутренней CustisWiki) Алгоритм сортировки слиянием применяется для сортировки, если есть возможность использовать для хранения промежуточных результатов память, сравнимую с размером исходного массива. Слияние — это объединение двух или более упорядоченных массивов в один упорядоченный. Пусть требуется упорядочить массив по убыванию. Для этого сравниваются два наименьших элемента обоих массивов и наименьший из них выводится как наименьший элемент суммарного массива, затем процедура повторяется (см. процедуру «merge» в представленном ниже алгоритме). Нетрудно видеть, что слияние двух упорядоченных последовательностей A и B длин |A| и |B| происходит за O(|A|+|B|) сравнений. Теперь рассмотрим алгоритм сортировки слиянием. Исходный массив A длины n делится пополам. Затем производится рекурсивная сортировка каждой половинки и их слияние. Пусть T(n) — число сравнений, достаточное для сортировки слиянием, тогда будет справедливо рекуррентное соотношение: Решив это соотношение, получаем, что сложность алгоритма асимптотически оптимальна — алгоритм сортирует входной массив за время O(n log n) для любых входных данных. Однако алгоритм сортировки слиянием редко применяется на практике, т. к. в процессе своей работы алгоритм активно использует дополнительные массивы, что редко допустимо в реальных приложениях. def mergesort(L): print funcname(),L if len(L) < 2: return L return merge(mergesort(L[:len(L)/2]),mergesort(L[len(L)/2:])) def merge(A,B): print funcname(),A,B, Out = [] while len(A)+len(B) > 0: if len(B) == 0 or (len(A) > 0 and A[0] < B[0]): Out.append(A[0]) A = A[1:] else: Out.append(B[0]) B = B[1:] print " -> ", Out return Out Sorting: [3, 4, 1, 5, 9, 2, 6, 5, 3, 5] mergesort: [3, 4, 1, 5, 9, 2, 6, 5, 3, 5] mergesort: [3, 4, 1, 5, 9] mergesort: [3, 4] mergesort: [3] mergesort: [4] merge: [3] [4] -> [3, 4] mergesort: [1, 5, 9] mergesort: [1] mergesort: [5, 9] mergesort: [5] mergesort: [9] merge: [5] [9] -> [5, 9] merge: [1] [5, 9] -> [1, 5, 9] merge: [3, 4] [1, 5, 9] -> [1, 3, 4, 5, 9] mergesort: [2, 6, 5, 3, 5] mergesort: [2, 6] mergesort: [2] mergesort: [6] merge: [2] [6] -> [2, 6] mergesort: [5, 3, 5] mergesort: [5] mergesort: [3, 5] mergesort: [3] mergesort: [5] merge: [3] [5] -> [3, 5] merge: [5] [3, 5] -> [3, 5, 5] merge: [2, 6] [3, 5, 5] -> [2, 3, 5, 5, 6] merge: [1, 3, 4, 5, 9] [2, 3, 5, 5, 6] -> [1, 2, 3, 3, 4, 5, 5, 5, 6, 9] Sorted: [1, 2, 3, 3, 4, 5, 5, 5, 6, 9]
Любые правки этой статьи будут перезаписаны при следующем сеансе репликации. Если у вас есть серьезное замечание по тексту статьи, запишите его в раздел «discussion». Репликация: База Знаний «Заказных Информ Систем» → «Сортировка слиянием» |
![]() |
![]() |
![]() |