Быстрая сортировка в Python
Python3 ПримерыБыстрая сортировка использует стратегию «разделяй и властвуй», чтобы разделить последовательность (список) на две подпоследовательности — с меньшими и большими элементами, затем рекурсивно сортирует эти две подпоследовательности.
Шаги:
- Выбор опорного значения: выберите элемент из последовательности, называемый «опорным»;
- Разбиение: переупорядочьте последовательность так, чтобы все элементы меньше опорного располагались перед опорным, а все элементы больше опорного — после опорного (числа, равные опорному, могут находиться с любой стороны). После завершения этого разбиения опорный элемент уже находится в своей окончательной отсортированной позиции;
- Рекурсивная сортировка подпоследовательностей: рекурсивно отсортируйте подпоследовательность элементов, меньших опорного, и подпоследовательность элементов, больших опорного.
Базовый случай рекурсии — когда размер последовательности равен нулю или единице; в этом случае последовательность, очевидно, уже отсортирована.
Существует несколько конкретных методов выбора опорного элемента. Этот метод выбора оказывает решающее влияние на временные характеристики сортировки.
Пример
def partition(arr,low,high):
i = ( low-1 ) # Индекс минимального элемента
pivot = arr[high]
for j in range(low , high):
# Текущий элемент меньше или равен опорному
if arr[j] <= pivot:
i = i+1
arr[i],arr[j] = arr[j],arr[i]
arr[i+1],arr[high] = arr[high],arr[i+1]
return ( i+1 )
# arr[] --> отсортированный массив
# low --> начальный индекс
# high --> конечный индекс
# Функция быстрой сортировки
def quickSort(arr,low,high):
if low < high:
pi = partition(arr,low,high)
quickSort(arr, low, pi-1)
quickSort(arr, pi+1, high)
arr = [10, 7, 8, 9, 1, 5]
n = len(arr)
quickSort(arr,0,n-1)
print ("Отсортированный массив:")
for i in range(n):
print ("%d" %arr[i]),
Результат выполнения приведённого выше кода:
排序后的数组: 1 5 7 8 9 10Другие расширения