Quicksort — это алгоритм сортировки типа "разделяй и властвуй", который выбирает опорный элемент, разбивает элементы на меньшие и большие, а затем рекурсивно сортирует обе части. В среднем O(n log n), в худшем случае O(n²).
Разбиение размещает опорный элемент на его окончательной позиции в отсортированном массиве; всё слева меньше, всё справа больше. Рекурсивно повторяй на обеих сторонах.
def quicksort(arr):
if len(arr) <= 1:
return arr
pivot = arr[len(arr) // 2] # pick a pivot
left = [x for x in arr if x < pivot] # smaller
mid = [x for x in arr if x == pivot] # equal
right = [x for x in arr if x > pivot] # larger
return quicksort(left) + mid + quicksort(right)
quicksort([5, 2, 8, 1, 3]) # -> [1, 2, 3, 5, 8]
(На практике используется разбиение на месте для экономии памяти.)
| Случай | Время | Причина |
|---|---|---|
| Лучший/Средний | O(n log n) | сбалансированные разбиения |
| Худший | O(n²) | уже отсортирован с плохим опорным элементом |
Quicksort на месте использует O(log n) стекового пространства.
Обычно самый быстрый на практике благодаря дружественности к кэшу и малым накладным расходам, и работает на месте. Худший случай O(n²) избегается с помощью случайного или median-of-three опорного элемента. Не стабилен.
Quicksort используется по умолчанию во многих стандартных библиотеках благодаря отличной скорости в среднем случае и низкому использованию памяти.
Понимание того, почему выбор опорного элемента приводит к худшему случаю O(n²), преподаёт важный урок: средний и худший случаи могут резко отличаться.
Это любимая тема на собеседованиях именно благодаря этому тонкому различию.