Python Quicksort
Python3-BeispieleQuicksort verwendet die Divide-and-Conquer-Strategie, um eine Sequenz (Liste) in zwei kleinere und größere Teilsequenzen zu unterteilen und diese beiden Teilsequenzen dann rekursiv zu sortieren.
Die Schritte sind:
- Wähle einen Pivot-Wert: Wähle ein Element aus der Sequenz, das als "Pivot" bezeichnet wird;
- Partitionierung: Ordne die Sequenz um; alle Elemente, die kleiner als das Pivot sind, werden vor das Pivot gesetzt, alle Elemente, die größer als das Pivot sind, werden hinter das Pivot gesetzt (Zahlen, die gleich dem Pivot sind, können auf beiden Seiten stehen). Nach dieser Partitionierung befindet sich das Pivot bereits an seiner endgültigen sortierten Position;
- Teilsequenzen rekursiv sortieren: Sortiere die Teilsequenz der Elemente, die kleiner als das Pivot sind, und die Teilsequenz der Elemente, die größer als das Pivot sind, rekursiv.
Der Basisfall der Rekursion ist, wenn die Größe der Sequenz null oder eins beträgt; in diesem Fall ist die Sequenz offensichtlich bereits sortiert.
Es gibt mehrere spezifische Methoden zur Auswahl des Pivots. Diese Auswahlmethode hat einen entscheidenden Einfluss auf das Zeitverhalten der Sortierung.
Beispiel
def partition(arr,low,high):
i = ( low-1 ) # Index des kleinsten Elements
pivot = arr[high]
for j in range(low , high):
# Aktuelles Element ist kleiner oder gleich dem Pivot
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[] --> Sortiertes Array
# low --> Startindex
# high --> Endindex
# Quicksort-Funktion
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 ("Sortiertes Array:")
for i in range(n):
print ("%d" %arr[i]),
Die Ausgabe beim Ausführen des obigen Codes ist:
排序后的数组: 1 5 7 8 9 10Weitere Erweiterungen