Описание тега quicksort
Quicksort - это алгоритм сортировки, изобретенный CAR Hoare, который имеет среднюю сложность O(n log n) и квадратичную сложность наихудшего случая. Это один из самых быстрых алгоритмов сортировки общего назначения.
Quicksort - это алгоритм сортировки, изобретенный CAR Hoare, который имеет среднюю сложность O(n log n) и квадратичную сложность наихудшего случая. Это один из самых быстрых алгоритмов сортировки общего назначения.
Быстрая сортировка имеет пространственную сложность O(1), поскольку элементы в массиве меняются местами, поэтому новые массивы не создаются.
Логика быстрой сортировки состоит в том, чтобы выбрать один из элементов и разделить список на два на основе этого элемента, с меньшим элементом в одном списке и большими элементами в другом списке, а затем отсортировать два списка.
На изображении ниже показана работа быстрой сортировки:
https://stackru.com/images/eeeb1ea5d6f5401dc39640790a72f91157e1cd14.gif