Курс 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"

  1. Операции с кортежами
  2. Управление User-Agent в Python
  3. Преобразование чисел в Python
  4. Лямбда-функции в Python
  5. Поиск шаблона в строке
  6. Работа с массивами в Python
  7. Кортеж в Python: создание и использование
  8. Проверка типа объекта в Python
  9. Функциональное программирование в Python
  10. Функции в одну строку
  11. Нахождение разницы между списками в Python
  12. Работа со словарями
  13. Python: изменяемые и неизменяемые коллекции
  14. Преобразование в float
  15. Распаковка с оператором *
  16. Генерация случайных чисел в Python
  17. Генерация случайных чисел в Python
  18. Установка максимального количества цифр
  19. Глобальные переменные в Python
  20. Оператор «or» в Python
  21. Метод difference_update() — разность множеств
  22. Работа с атрибутом dict
  23. Статическая типизация в Python
  24. Конкатенация строковых литералов
  25. Работа с байтовыми строками в Python
  26. Поиск индекса элемента в списке
  27. Работа с классами данных
  28. Профилирование данных с Pandas
  29. Генераторы списков в Python
  30. Аннотации типов в Python
  31. Отладка кода
  32. Замер времени выполнения кода
  33. Переопределение метода
  34. Вызов функций по строке в Python.
  35. Подсчет элементов в Python
  36. Объединение словарей в Python
  37. Инициализация объекта
  38. HTTP-запросы с библиотекой Requests
  39. Создание списков в Python
  40. Определение функций с необязательными аргументами
  41. Получение комбинаций в Python
  42. Генерация строк с .join()
  43. Работа с часовыми поясами в Python.
  44. Работа с f-строками 2.0
  45. Фильтрация списков с itertools
  46. Декораторы в Python
  47. Удаление элементов из списка в Python
  48. Условные выражения в Python

Marketello читают маркетологи из крутых компаний