PYTHON СОРТИРОВКА СЛИЯНИЕМ РЕКУРСИЯ
Сортировка слиянием - это алгоритм сортировки, использующий метод разделяй и властвуй. Он основан на слиянии отсортированных подмассивов, которые были рекурсивно разделены на две части.
Алгоритм следующий:
def merge_sort(arr): if len(arr) > 1: mid = len(arr) // 2 left_half = arr[:mid] right_half = arr[mid:] merge_sort(left_half) merge_sort(right_half) i = 0 j = 0 k = 0 while i < len(left_half) and j < len(right_half): if left_half[i] < right_half[j]: arr[k] = left_half[i] i += 1 else: arr[k] = right_half[j] j += 1 k += 1 while i < len(left_half): arr[k] = left_half[i] i += 1 k += 1 while j < len(right_half): arr[k] = right_half[j] j += 1 k += 1Код сначала разбивает массив на две части до тех пор, пока каждый из них не будет состоять из одного элемента. Затем он рекурсивно объединяет каждую половину, сравнивая элементы между собой. После объединения двух половин массива, этот процесс повторяется до тех пор, пока весь массив не будет отсортирован.
Сортировка слиянием обладает сложностью времени O(n*log(n)). Это делает ее быстрее, чем большинство других алгоритмов сортировки со сложностью времени O(n^2).
Сортировка слиянием в python. Merge sort in Python. Recursive sorting algorithms
Merge Sort in Python Programming - Example
Алгоритмы на Python 3. Лекция №1
Алгоритмы. Сортировка слиянием. Рекурсивный алгоритм. Реализация на Python и Java.
Merge Sort Code in Python
#12. Быстрая сортировка слиянием (merge sort) - Алгоритмы на Python
Сортировка слиянием против быстрой сортировки
#11. Слияние двух упорядоченных списков - Алгоритмы на Python
Новые материалы: