Структуры данных - алгоритм сортировки слиянием
Сортировка слиянием - это метод сортировки, основанный на технике «разделяй и властвуй». С временной сложностью наихудшего случая, равной Ο (n log n), это один из наиболее уважаемых алгоритмов.
Сортировка слиянием сначала делит массив на равные половины, а затем объединяет их в отсортированном порядке.
Как работает сортировка слиянием?
Чтобы понять сортировку слиянием, мы берем несортированный массив следующим образом:
Мы знаем, что сортировка слиянием сначала итеративно делит весь массив на равные половины, если не достигнуты атомарные значения. Здесь мы видим, что массив из 8 элементов разделен на два массива размером 4.
Это не меняет последовательность появления предметов в оригинале. Теперь разделим эти два массива пополам.
Далее мы разделяем эти массивы и получаем атомарное значение, которое больше не может быть разделено.
Теперь мы объединяем их точно так же, как они были разбиты. Обратите внимание на цветовые коды, указанные в этих списках.
Сначала мы сравниваем элементы для каждого списка, а затем объединяем их в другой список отсортированным способом. Мы видим, что 14 и 33 находятся в отсортированных позициях. Мы сравниваем 27 и 10 и в целевом списке из 2 значений ставим сначала 10, а затем 27. Мы меняем порядок 19 и 35, тогда как 42 и 44 размещаются последовательно.
На следующей итерации фазы объединения мы сравниваем списки двух значений данных и объединяем их в список найденных значений данных, размещая все в отсортированном порядке.
После окончательного объединения список должен выглядеть так -
Теперь мы должны изучить некоторые программные аспекты сортировки слиянием.
Алгоритм
Сортировка слиянием продолжает делить список на равные половины до тех пор, пока его больше нельзя будет разделить. По определению, если это только один элемент в списке, он сортируется. Затем сортировка слиянием объединяет меньшие отсортированные списки, сохраняя при этом сортировку нового списка.
Step 1 − if it is only one element in the list it is already sorted, return.
Step 2 − divide the list recursively into two halves until it can no more be divided.
Step 3 − merge the smaller lists into new list in sorted order.
Псевдокод
Теперь мы увидим псевдокоды для функций сортировки слиянием. Как показывают наши алгоритмы, две основные функции - разделить и объединить.
Сортировка слиянием работает с рекурсией, и мы увидим нашу реализацию точно так же.
procedure mergesort( var a as array )
if ( n == 1 ) return a
var l1 as array = a[0] ... a[n/2]
var l2 as array = a[n/2+1] ... a[n]
l1 = mergesort( l1 )
l2 = mergesort( l2 )
return merge( l1, l2 )
end procedure
procedure merge( var a as array, var b as array )
var c as array
while ( a and b have elements )
if ( a[0] > b[0] )
add b[0] to the end of c
remove b[0] from b
else
add a[0] to the end of c
remove a[0] from a
end if
end while
while ( a has elements )
add a[0] to the end of c
remove a[0] from a
end while
while ( b has elements )
add b[0] to the end of c
remove b[0] from b
end while
return c
end procedure
Чтобы узнать о реализации сортировки слиянием на языке программирования C, нажмите здесь .