Austauschsortierung – Blasensortierung (Bubble Sort)

Bei der Austauschsortierung werden hauptsächlich die Schlüsselcodes der zu sortierenden Datensätze paarweise verglichen. Wenn die Schlüsselcodes der zu sortierenden Datensätze vorkommen, werden sie ausgetauscht, wenn sie den Sortieranforderungen widersprechen. Schauen wir uns zunächst den Blasenprozess beim Sortieren von Spalten an: Seien 1
lautet:

i=1; // Richten Sie den paarweisen Vergleich ab dem ersten Datensatz ein.

Wenn i≥j, A sprudelt Die Reise ist vorbei.

Vergleichen Sie r[i].key und r[i+1].key. Wenn r[i].key≤r[i+1].key, nicht austauschen, weiter mit ⑤

Wenn r[i].key>r[i+1].key, r[0]=r[i]; [ 0]; Tauschen Sie r[i] und r[i+1] aus

i=i+1; Passen Sie die nächsten beiden Datensätze an, um sie paarweise zu vergleichen, gehen Sie zu ②

Blasensortiermethode: Für eine Tabelle mit n Datensätzen dient die erste Blase dazu, einen Datensatz r[n] mit dem größten Schlüsselcode zu erhalten. Die zweite Blase dient für eine Tabelle mit n-1 Datensätzen und einen weiteren Datensatz mit dem größten Schlüssel Code wird erhalten. Zeichnen Sie r[n-1] auf und wiederholen Sie dies, bis sich n Datensätze in einer nach Schlüsseln geordneten Tabelle befinden.

[Algorithmus 10.6]

j=n; //Beginne aus der Tabelle mit n Datensätzen

Wenn j

i=1; // Eine Blasenfahrt, paarweise Vergleich beginnend mit dem ersten Datensatz einrichten,

Wenn i≥j, endet eine Blasenfahrt, j=j-1; der Datensätze ist -1, gehen Sie zu ②

, um r[i].key und r[i+1].key zu vergleichen, wenn r[i].key≤r[i+1].key, nicht austauschen, Gehe zu ⑤

Wenn r[i].key>r[i+1].key, r[i]r[i+1]; i] und r [i+1] Tauschen Sie

i=i+1; passen Sie den paarweisen Vergleich der nächsten beiden Datensätze an und wechseln Sie zu ④

[Effizienzanalyse]
Platzeffizienz: Es wird nur ein Zusatzgerät verwendet.

Zeiteffizienz: Insgesamt sind n-1 Bubbling-Operationen für eine Tabelle mit j Datensätzen erforderlich.

Anzahl der Verschiebungen:

Bester Fall: Die zu sortierende Spalte ist bereits in Ordnung, kein Verschieben erforderlich

Schlechtester Fall: jeder Vergleich Nach jedem Schritt sind drei Schritte erforderlich.

Bitte achten Sie auf weitere Informationen zum Austauschsortieren und Blasensortieren (Bubble Sort). Artikel. PHP Chinesische Website!