Quick Sort
Quick Sort — быстрый алгоритм сортировки, основанный на разбиении массива относительно опорного элемента.
Основная идея
Выбираем pivot, переносим меньшие элементы влево, большие — вправо, затем рекурсивно сортируем части.
Пошаговый пример
Исходный массив:
[7, 2, 9, 4, 3, 8]- Pivot = 8, после partition получаем ... 8 на правильной позиции
- Рекурсивно сортируем левую часть
- После нескольких partition получаем [2,3,4,7,8,9]
Псевдокод
quick_sort(arr, left, right):
if left >= right: return
pivot_index = partition(arr, left, right)
quick_sort(arr, left, pivot_index - 1)
quick_sort(arr, pivot_index + 1, right)
Оптимизация: Используйте random pivot или median-of-three, чтобы снизить риск худшего случая.
Сложность
Время
O(n log n) в среднем, O(n²) в худшем случае.
Память
O(log n) на стек рекурсии в среднем.
Когда используется
- Общая сортировка в памяти
- Высокая производительность на практике
- Встроенные сортировки
Ключевые свойства
- Не стабильный
- Обычно in-place
- Очень быстрый в среднем