Курс 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. Оптимизация гиперпараметров в Python
  3. Многоточие в Python
  4. Разработка игры Pong с turtle
  5. Получение частей дроби
  6. Генератор списка с условием if
  7. Отступы в Python
  8. CLI-инструмент howdoi
  9. Лямбда-функции в Python
  10. ChainMap.new_child() — добавление нового словаря
  11. Работа с асинхронными задачами в Python
  12. Работа с аргументами командной строки в Python
  13. Извлечение новостей с помощью newspaper3k
  14. Изменяемые и неизменяемые объекты
  15. Сортировка элементов с OrderedDict
  16. Обрезка изображения с Pillow
  17. Конвертация изображений в PDF
  18. Docstring в Python
  19. Комментарии в Python
  20. Вызов функций по строке в Python.
  21. Метод index() в Python
  22. Определение локальных переменных в Python
  23. Обработка аргументов Python
  24. Создание вложенных циклов for
  25. Создание словаря с значением по умолчанию
  26. Отслеживание выполнения программы с библиотекой tqdm
  27. Исключение NotImplementedError
  28. Оператор Walrus в Python
  29. Создание уникального проекта
  30. Вычисление времени выполнения
  31. Замена переменных в Python
  32. Переменные в Python: сокращение гласных
  33. Простой калькулятор Python
  34. Работа с изменяемыми коллекциями
  35. Метод setdefault() в Python
  36. Обучение модели с указанием эпох
  37. Конкатенация списков в Python
  38. Работа с модулем os в Python
  39. Модуль future Python
  40. Извлечение аудио из видео
  41. Избегайте использования goto
  42. Создание вложенного генератора
  43. Работа со временем в Python
  44. Асинхронное выполнение задач в Python
  45. Поиск частых элементов в списке

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