J'ai écrit une note pour moi-même sur le tri rapide.
quick_sort.py
def partition(A, p, r):
x = A[r-1]
i = p-1
for j in range(p, r-1):
if A[j] <= x:
i += 1
A[i], A[j] = A[j], A[i]
A[i+1], A[r-1] = A[r-1], A[i+1]
return i+1
n = int(input())
A = list(map(int, input().split()))
def quick_sort(A, p, r):
if p < r:
q = partition(A, p, r)
quick_sort(A, p, q)
quick_sort(A, q+1, r)
return A
print(quick_sort([3, 1, 10, 2.5, 11, 3, 21,4, -1], 0, 9))
# [-1, 1, 2.5, 3, 3, 4, 10, 11, 21]
Puisque l'algorithme ci-dessus a une sélection constante de critères (la dernière valeur), il sera inefficace en fonction de la disposition des données. Le montant du calcul peut être O (n ^ 2) Les récurrences peuvent être trop profondes et une erreur peut se produire Par conséquent, il est nécessaire de concevoir des moyens de sélectionner des critères tels que la randomisation et la sélection de la valeur médiane.