Python Bubblesort
Python3-BeispieleBubblesort ist ein einfacherAustausch-Sortieralgorithmus, und sein grundlegendes Funktionsprinzip ist:
- Die zu sortierende Liste wiederholt durchlaufen und dabeizwei benachbarte Elemente vergleichen；
- Wenn die Reihenfolge der beiden Elemente nicht den Anforderungen entspricht (zum Beispiel ist bei aufsteigender Sortierung das vorherige Element größer als das nächste), danntausche ihre Positionen；
- Jede Runde des Durchlaufs verschiebt dasgrößte Element im aktuell unsortierten Teil durch Aufsteigenlassen ans Ende(Szenario aufsteigender Reihenfolge), genau wie Blasen nach oben steigen;
- Wiederhole den obigen Vorgang, bis die gesamte Liste vollständig sortiert ist (keine Tauschvorgänge stattfinden oder alle Elemente durchlaufen wurden).
Hauptmerkmale
- Sortierart: Austauschsortierung
- Zeitkomplexität: schlechtester Fall O(n²) (Liste vollständig in umgekehrter Reihenfolge), durchschnittlicher Fall O(n²), bester Fall O(n) (optimierte Version, Liste bereits sortiert)
- Speicherkomplexität: O(1) (In-place-Sortierung, kein zusätzlicher Hilfsspeicher erforderlich)
- Stabilität: stabiler Sortieralgorithmus (die relativen Positionen gleicher Elemente ändern sich nicht)
Beispiel
def bubbleSort(arr):
n = len(arr)
# Alle Array-Elemente durchlaufen
for i in range(n):
# Die letzten i Elemente sind bereits an der richtigen Position (kein erneuter Vergleich nötig)
for j in range(0, n-i-1):
if arr[j] > arr[j+1] :
arr[j], arr[j+1] = arr[j+1], arr[j]
arr = [64, 34, 25, 12, 22, 11, 90]
bubbleSort(arr)
print ("Sortiertes Array:")
for i in range(len(arr)):
print ("%d" %arr[i]),
Die Ausgabe beim Ausführen des obigen Codes ist:
排序后的数组: 11 12 22 25 34 64 90Andere Erweiterungen