Курс Python → Сортировка слиянием
Алгоритм сортировки слиянием является одним из наиболее эффективных методов сортировки массивов. Он основан на стратегии «разделяй и властвуй», которая заключается в разделении исходного массива на две равные части, сортировке каждой из них отдельно, а затем объединении отсортированных подмассивов в один отсортированный массив. Этот подход позволяет эффективно сортировать массивы любого размера.
Для реализации алгоритма сортировки слиянием на Python можно написать функцию, которая будет рекурсивно разделять и сортировать массив. Начнем с базового случая — когда массив содержит только один элемент, в этом случае он уже отсортирован. Затем рекурсивно делим массив пополам, пока не дойдем до базового случая, после чего начинаем объединять и сортировать подмассивы.
def merge_sort(arr):
if len(arr) <= 1:
return arr
mid = len(arr) // 2
left = merge_sort(arr[:mid])
right = merge_sort(arr[mid:])
return merge(left, right)
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
arr = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5]
sorted_arr = merge_sort(arr)
print(sorted_arr)
В данном примере функция merge_sort рекурсивно разделяет и сортирует массив arr, а функция merge объединяет и сортирует два отсортированных подмассива. После вызова merge_sort для исходного массива, мы получаем отсортированный массив sorted_arr, который затем можно использовать в дальнейшем коде.
Алгоритм сортировки слиянием имеет сложность O(n log n), что делает его одним из наиболее эффективных методов сортировки. Он также устойчив, что означает, что порядок элементов с одинаковыми значениями не меняется после сортировки. Этот алгоритм широко используется в практике программирования и может быть полезен при работе с большими массивами данных.
Другие уроки курса "Python"
- Операции с кортежами
- Управление User-Agent в Python
- Преобразование чисел в Python
- Лямбда-функции в Python
- Поиск шаблона в строке
- Работа с массивами в Python
- Кортеж в Python: создание и использование
- Проверка типа объекта в Python
- Функциональное программирование в Python
- Функции в одну строку
- Нахождение разницы между списками в Python
- Работа со словарями
- Python: изменяемые и неизменяемые коллекции
- Преобразование в float
- Распаковка с оператором *
- Генерация случайных чисел в Python
- Генерация случайных чисел в Python
- Установка максимального количества цифр
- Глобальные переменные в Python
- Оператор «or» в Python
- Метод difference_update() — разность множеств
- Работа с атрибутом dict
- Статическая типизация в Python
- Конкатенация строковых литералов
- Работа с байтовыми строками в Python
- Поиск индекса элемента в списке
- Работа с классами данных
- Профилирование данных с Pandas
- Генераторы списков в Python
- Аннотации типов в Python
- Отладка кода
- Замер времени выполнения кода
- Переопределение метода
- Вызов функций по строке в Python.
- Подсчет элементов в Python
- Объединение словарей в Python
- Инициализация объекта
- HTTP-запросы с библиотекой Requests
- Создание списков в Python
- Определение функций с необязательными аргументами
- Получение комбинаций в Python
- Генерация строк с .join()
- Работа с часовыми поясами в Python.
- Работа с f-строками 2.0
- Фильтрация списков с itertools
- Декораторы в Python
- Удаление элементов из списка в Python
- Условные выражения в Python















