Учебное пособие по алгоритму сортировки слиянием Python
Узнайте, как реализовать сортировку слиянием в Python. Интерактивный пошаговый пример стратегии сортировки «Разделяй и властвуй».
Обзор
Сортировка слиянием — это высокоэффективный алгоритм сортировки, использующий стратегию «разделяй и властвуй». Он разбивает несортированный список на более мелкие подсписки, сортирует эти подсписки, а затем снова объединяет их вместе.
Алгоритм рекурсивно разбивает массив пополам, пока не достигнет одноэлементных подмассивов. Затем он объединяет отсортированные подмассивы, сравнивая элементы с каждой стороны и размещая их в отсортированном порядке. Это обеспечивает оптимальную временную сложность.
Независимо от того, является ли исходный массив отсортированным, перевернутым или полностью случайным, сортировка слиянием выполняется за время O(n log n). Однако для хранения подсписков на этапе слияния требуется дополнительное пространство O(n).
Код и вывод выполнения
Стандартная рекурсивная реализация алгоритма сортировки слиянием в Python.
def merge_sort(arr):
if len(arr) <= 1:
return arr
mid = len(arr) // 2
left_half = merge_sort(arr[:mid])
right_half = merge_sort(arr[mid:])
return merge(left_half, right_half)
def merge(left, right):
result = []
i = j = 0
while i < len(left) and j < len(right):
if left[i] < right[j]:
result.append(left[i])
i += 1
else:
result.append(right[j])
j += 1
result.extend(left[i:])
result.extend(right[j:])
return result
# Test dataset
data = [38, 27, 43, 3, 9, 82, 10]
print("Original List:", data)
sorted_data = merge_sort(data)
print("Sorted List: ", sorted_data)Original List: [38, 27, 43, 3, 9, 82, 10]
Sorted List: [3, 9, 10, 27, 38, 43, 82]Пошаговая реализация
- Сортировка связанных списков, где структура узлов облегчает объединение без копирования.
- Внешние процедуры сортировки файлов, которые не полностью помещаются в системную оперативную память.
- Стабильные приложения сортировки, в которых совпадающие ключи должны сохранять свой первоначальный порядок.
Часто задаваемые вопросы
Является ли сортировка слиянием стабильным алгоритмом сортировки?
Да, сортировка слиянием стабильна. При сравнении идентичных элементов первым помещается элемент из левого (исходный первый) подмассива, сохраняя их исходные относительные позиции.
Почему Python использует Timsort вместо чистой сортировки слиянием?
Встроенный в Python метод sorted() использует Timsort — гибридный алгоритм, сочетающий в себе сортировку слиянием и сортировку вставками. Он оптимизирует шаблоны реальных данных, определяя уже отсортированные подсегменты, обрабатывая их быстрее, чем чистая сортировка слиянием.
Связанные темы
Изучите алгоритм быстрой сортировки в Python. Изучите выбор опорной точки, секционирование и рекурсию в этом интерактивном примере кодирования.
Алгоритмы сортировки PythonИзучите алгоритмы сортировки Python. Визуализируйте пузырьковую сортировку и сортировку слиянием в контексте IDE браузера.
Алгоритм двоичного поиска PythonПоиск в отсортированных списках осуществляется за логарифмическое время O(log n). Запускайте и разбирайтесь в двоичном поиске в Python, включая пошаговую логику, крайние случаи и оптимизации.