Курс 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"
- Комментарии в Python
- Циклы for в Python
- Экспорт данных с помощью writefile
- Итераторы с потерямиZIP
- Работа с кортежами
- Функция divmod() в Python
- Основы слова
- Создание списка через цикл
- Извлечение статей с newspaper3k
- Создание вкладок с TKinter
- Метод ifloordiv для пользовательских классов
- Перемешивание списка с shuffle()
- Функции высшего порядка в Python
- Сортировка данных с лямбда-функциями
- Подсчет вхождений элементов
- Определение относительного пути
- Работа с дробями в Python
- Удаление специальных символов
- Проверка окончания строки с помощью str.endswith()
- Поиск подстроки в строке
- Показ всплывающих окон Tkinter
- Форматирование строк в Python
- Комментарии в Python
- Аннотации типов в Python
- Глобальные переменные в Python
- Проверка переменных окружения в Python
- Преобразование данных в Python
- Справка по импортированным модулям
- Частичное совпадение пользовательского ввода в Python 3.10
- Многострочные комментарии в Python
- Оператор in в Python
- Удаление первого элемента списка
- Математические функции в Python
- Создание класса в Python
- Модуль inspect
- Генераторы в Python
- Проверка типа данных
- Шаблоны Flask: условия и циклы
- Работа со словарями Python
- Проверка элемента в множестве.
- Лямбда-функции в Python
- IPython и Jupyter Notebook: руководство
- Ошибка NotImplemented в Python
- Модуль math: константы π и e















