Рекурсивный алгоритм «разделяй и властвуй».
Быстрая сортировка — это широко используемый алгоритм сортировки, временная сложность которого в лучшем случае составляет O(n log n), а в худшем — O(n²). В худшем случае сортируемый массив уже отсортирован или почти отсортирован.
Быстрая сортировка работает, выбирая элемент массива в качестве «стержня», а затем разделяя массив на два раздела. Один раздел для значений меньше сводного и один раздел для тех, что больше.
Сегодня мы рассмотрим реализацию быстрой сортировки, которая выполняет сортировку массива целых чисел, но ее можно легко адаптировать для сортировки чего угодно с помощью правильной функции сравнения.
Пограничные случаи
- Пустой массив или массив только с 1 элементом не подлежит сортировке, поэтому верните входной массив.
Теперь я собираюсь создать переменную длины (для удобства), опорную точку и оба раздела, которые мы будем рекурсивно сортировать. Я устанавливаю точку поворота последним элементом массива для простоты, но есть и другие, более сложные, но и более эффективные способы установки точки поворота. См. схему разделов Хора.
Теперь, когда наши разделы настроены, мы можем выполнить итерацию по массиву, помещая значения ниже опорного в левом разделе и значения выше опорного в правом разделе.
Теперь у нас есть полусортированный массив с левым разделом, сводным и правым разделом. Осталось только рекурсивно отсортировать левый и правый разделы и соединить их.
Этот алгоритм работает быстро, когда заданы массивы, которые еще не отсортированы. Однако это простая реализация быстрой сортировки с большими возможностями для оптимизации.
Разделение в этой реализации быстрой сортировки создает два новых массива в памяти при каждом вызове функции, это может складываться, если у вас большой входной массив. Если вы не возражаете против мутации входного массива напрямую, вы можете сэкономить много памяти, поменяв местами элементы в исходном массиве во время разбиения вместо создания новых пустых массивов для отправки.
Вот та же реализация быстрой сортировки в Python.
