Быстрая сортировка (quick sort) в Python
В этом уроке вы реализуете быструю сортировку, разделяя список относительно опорного элемента.
Введение
Какую задачу это решает
Быстрая сортировка - одна из самых распространённых идей сортировки, потому что в среднем она быстра и её легко выразить. Она показывает ещё один способ делить задачу: не пополам, а вокруг выбранного значения.
Пример из жизни
Быстрая сортировка похожа на сортировку книг по высоте вокруг одной выбранной книги. Все книги пониже кладутся в левую стопку, повыше - в правую, а книги той же высоты - в середину. Потом каждая боковая стопка сортируется так же, и стопки собираются вместе.
pivot = values[len(values) // 2]📕 Выбрать книгу для сравненияlower = [... if value < pivot]⬅️ Книги пониже налевоhigher = [... if value > pivot]➡️ Книги повыше направоquick_sort(lower) + equal + quick_sort(higher)📚 Отсортировать каждую сторону, потом соединить стопкиБыстрая сортировка выбирает опорный элемент, делит остальные элементы на меньшие и большие него, рекурсивно сортирует каждую часть и соединяет их; в среднем это время O(n log n).
Главное
if len(values) <= 1:- базовый случай: такой список уже отсортирован.pivot = values[len(values) // 2]берёт среднее значение как опорное.lower,equalиhigherделят значения вокруг опорного;equalдержит повторы вместе.quick_sort(lower) + equal + quick_sort(higher)сортирует две стороны и соединяет три списка.
Когда это нужно?
- Знакомство с разбиением и рекурсией.
- Универсальная сортировка на месте в языках и библиотеках (с аккуратным выбором опорного).
- Задачи выбора, например поиск медианы (quickselect использует то же разбиение).
Когда это не нужно
- Обычный код на Python:
sorted()быстрее и устойчив. - Когда важен гарантированный худший случай: при плохих опорных быстрая сортировка становится
O(n²), а сортировка слиянием - никогда.
Визуализация: Быстрая сортировка (quick sort) в Python
O(n log n)Нажимайте Запуск или Шаг, чтобы следить за сравнениями и перемещением данных.
Пример кода
def quick_sort(values):
if len(values) <= 1:
return values
pivot = values[len(values) // 2]
lower = [value for value in values if value < pivot]
equal = [value for value in values if value == pivot]
higher = [value for value in values if value > pivot]
return quick_sort(lower) + equal + quick_sort(higher)
print(quick_sort([10, 7, 8, 9, 1, 5]))
Результат выполнения
[1, 5, 7, 8, 9, 10]
Разбор кода
Эта легко читаемая версия выбирает опорным средний элемент и с помощью генераторов списков создаёт три списка: lower, equal и higher. Результат складывается из quick_sort(lower), equal и quick_sort(higher). Средняя сложность O(n log n), но при неудачном выборе опорного элемента алгоритм может замедлиться до O(n²).
Измените значения и запустите программу в онлайн-компиляторе Python CodeUtility без локальной установки Python.
Упражнения для практики
Попробуйте изменить код по подсказкам ниже. Если менять код и смотреть на результат, урок запомнится гораздо лучше, чем при простом чтении.
- Проверьте работу на пустом списке, списке из одного элемента и списке с повторами.
- Выводите состояние после каждого шага, чтобы увидеть алгоритм в действии.
- Измерьте время работы на 100, 1 000 и 10 000 элементах и сравните с другим решением.
Частые ошибки
Потеря значений, равных опорному
Если оставить только < и >, повторы опорного исчезнут.
return quick_sort(lower) + [pivot] + quick_sort(higher)
return quick_sort(lower) + equal + quick_sort(higher)
Закончили этот урок?
Отметьте его как изученный, чтобы следить за прогрессом.
Попрактикуйтесь на задаче
Примените материал этого урока к реальной задаче. Каждая задача запускается в браузере, с мгновенными тестами и разбором от ИИ.
Все задачи