Blasensortierung

Eine Blasensortierung sortiert das Array in mehreren Phasen. Bei jedem Durchgang werden die benachbarten Elemente nacheinander vertauscht, wenn die Elemente nicht in der richtigen Reihenfolge sind. Der Blasensortierungsalgorithmus führt mehrere Durchläufe durch das Array durch. Bei jedem Durchgang werden aufeinanderfolgende Nachbarpaare verglichen. Liegt ein Paar in absteigender Reihenfolge vor, werden seine Werte vertauscht; andernfalls bleiben die Werte unverändert. Die Technik wird als Blasensortierung oder sinkende Sortierung bezeichnet, da die kleineren Werte nach und nach nach oben „sprudeln“ und die größeren Werte nach unten sinken. Nach dem ersten Durchgang wird das letzte Element zum größten im Array. Nach dem zweiten Durchgang wird das vorletzte Element zum zweitgrößten im Array. Dieser Vorgang wird fortgesetzt, bis alle Elemente sortiert sind.

Die Abbildung unten (a) zeigt den ersten Durchgang einer Blasensortierung für ein Array von sechs Elementen (2 9 5 4 8 1). Vergleichen Sie die Elemente im ersten Paar (2 und 9), und es ist kein Austausch erforderlich, da sie bereits in der richtigen Reihenfolge sind. Vergleichen Sie die Elemente im zweiten Paar (9 und 5) und tauschen Sie 9 mit 5, da 9 größer als 5 ist. Vergleichen Sie die Elemente im dritten Paar (9 und 4) und tauschen Sie 9 mit 4. Vergleichen Sie die Elemente im vierten Paar (9 und 8) und tauschen Sie 9 mit 8. Vergleichen Sie die Elemente im fünften Paar (9 und 1) und tauschen Sie 9 mit 1. Die verglichenen Paare werden hervorgehoben und die bereits sortierten Zahlen sind in der Abbildung unten kursiv dargestellt.

Der erste Durchgang platziert die größte Zahl (9) als letzte im Array. Im zweiten Durchgang, wie in Abbildung unten (b) dargestellt, vergleichen und ordnen Sie Elementpaare der Reihe nach. Das letzte Paar muss nicht berücksichtigt werden, da das letzte Element im Array bereits das größte ist. Im dritten Durchgang, wie in Abbildung unten (c) dargestellt, vergleichen und ordnen Sie Elementpaare der Reihe nach, mit Ausnahme der letzten beiden Elemente, da diese bereits in der richtigen Reihenfolge sind. Im k-ten Durchgang müssen Sie also die letzten k-1 Elemente nicht berücksichtigen, da diese bereits geordnet sind.

Der Algorithmus für eine Blasensortierung wird im folgenden Code beschrieben.

for (int k = 1; k < list.length; k++) {
// Führe den k-ten Durchgang aus
for (int i = 0; i < list.length - k; i++) {
if (list[i] > list[i + 1])
tausche list[i] mit list[i + 1];
}
}

Beachten Sie, dass, wenn in einem Durchgang kein Austausch stattfindet, keine Notwendigkeit besteht, den nächsten Durchgang durchzuführen, da alle Elemente bereits sortiert sind. Sie können diese Eigenschaft verwenden, um den Algorithmus im Code oben wie im Code unten zu verbessern.

boolean needNextPass = true;
for (int k = 1; k < list.length && needNextPass; k++) {
// Das Array wird möglicherweise sortiert und der nächste Durchgang ist nicht erforderlich
needNextPass = false;
// Führe den k-ten Durchgang aus
for (int i = 0; i < list.length – k; i++) {
if (list[i] > list[i + 1]) {
tausche list[i] mit list[i + 1];
needNextPass = true; // Nächster Durchgang noch nötig
}
}
}

Der Algorithmus kann im folgenden Code implementiert werden

Im besten Fall benötigt der Blasensortierungsalgorithmus nur den ersten Durchgang, um festzustellen, dass das Array bereits sortiert ist – ein nächster Durchgang ist nicht erforderlich. Da die Anzahl der Vergleiche im ersten Durchgang n – 1 beträgt, ist die beste Zeit für eine Blasensortierung O(n).

Im schlimmsten Fall erfordert der Blasensortierungsalgorithmus n – 1 Durchgänge. Der erste Durchgang führt n – 1 Vergleiche durch; der zweite Durchgang führt n – 2 Vergleiche durch; und so weiter; Der letzte Durchgang führt 1 Vergleich durch. Somit beträgt die Gesamtzahl der Vergleiche:

Daher ist die ungünstigste Zeit für eine Blasensortierung O(n^2).

Das obige ist der detaillierte Inhalt vonBlasensortierung. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!