Ich habe mir eine Notiz über das schnelle Sortieren geschrieben.
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]
Da der obige Algorithmus eine konstante Auswahl von Kriterien (den letzten Wert) aufweist, ist er abhängig von der Anordnung der Daten ineffizient. Der Berechnungsbetrag kann O (n ^ 2) sein. Die Wiederholungen sind möglicherweise zu tief und es kann ein Fehler auftreten Daher müssen Möglichkeiten zur Auswahl von Kriterien wie Randomisierung und Auswahl des Medianwerts entwickelt werden.
Sortieralgorithmus und Implementierung in Python
Recommended Posts