Руководство по алгоритму быстрой сортировки Python
Изучите алгоритм быстрой сортировки в Python. Изучите выбор опорной точки, секционирование и рекурсию в этом интерактивном примере кодирования.
Обзор
Быстрая сортировка — чрезвычайно быстрый и широко используемый алгоритм сортировки. Как и сортировка слиянием, здесь используется подход «разделяй и властвуй». Однако быстрая сортировка сортирует элементы «на месте», что позволяет эффективно использовать память.
Алгоритм работает путем выбора «поворотного» элемента из списка. Затем он разделяет другие элементы на два подмассива: те, которые меньше опорной точки, и те, которые больше опорной точки. Этот процесс рекурсивно применяется к подмассивам.
Хотя сложность быстрой сортировки в наихудшем случае равна O(n²), среднее время ее выполнения составляет O(n log n), и на практике она обычно превосходит сортировку слиянием из-за меньшего количества промахов в кэше и нулевых затрат на создание временных массивов.
Код и вывод выполнения
Краткий рекурсивный сценарий быстрой сортировки, использующий списки для повышения удобства чтения.
def quicksort(arr):
if len(arr) <= 1:
return arr
else:
pivot = arr[len(arr) // 2]
left = [x for x in arr if x < pivot]
middle = [x for x in arr if x == pivot]
right = [x for x in arr if x > pivot]
return quicksort(left) + middle + quicksort(right)
# Test list
data = [12, 4, 5, 6, 7, 3, 1, 15]
print("Original List:", data)
sorted_data = quicksort(data)
print("Sorted List: ", sorted_data)Original List: [12, 4, 5, 6, 7, 3, 1, 15]
Sorted List: [1, 3, 4, 5, 6, 7, 12, 15]Пошаговая реализация
- Системные процедуры сортировки, при которых объем памяти должен быть сведен к минимуму.
- Сортировка общего назначения в рамках стандартных языковых библиотек
- Академическое обучение механике разделов и рекурсивному принципу «разделяй и властвуй».
Часто задаваемые вопросы
Как мы можем избежать наихудшей сложности O(n²) в быстрой сортировке?
Худший случай возникает, когда выбранный опорный элемент неоднократно оказывается наименьшим или наибольшим элементом. Чтобы смягчить это, разработчики используют такие стратегии, как выбор случайного опорного значения или значений «медианы из трех».
Быстрая сортировка стабильна?
Нет, стандартная быстрая сортировка нестабильна. Во время секционирования элементы меняются местами в больших диапазонах, что может изменить относительный порядок повторяющихся элементов.
Связанные темы
Узнайте, как реализовать сортировку слиянием в Python. Интерактивный пошаговый пример стратегии сортировки «Разделяй и властвуй».
Алгоритмы сортировки PythonИзучите алгоритмы сортировки Python. Визуализируйте пузырьковую сортировку и сортировку слиянием в контексте IDE браузера.
Алгоритм двоичного поиска PythonПоиск в отсортированных списках осуществляется за логарифмическое время O(log n). Запускайте и разбирайтесь в двоичном поиске в Python, включая пошаговую логику, крайние случаи и оптимизации.