Prinzip
Blasensortierung ist wahrscheinlich ein Algorithmus, den alle Programmierer verwenden können, und ist auch einer der bekanntesten Algorithmen.
Seine Ideen sind nicht kompliziert:
Angenommen, das Array arr [] ist jetzt sortiert und hat n Elemente.
1. Wenn n = 1: Offensichtlich müssen sich nicht anstellen. (Tatsächlich scheint diese Diskussion unnötig zu sein)
2. Wenn n> 1:
(1) Wir beginnen mit dem ersten Element und vergleichen alle zwei benachbarten Elemente. Wenn das vorherige Element größer als das nächste ist, wird der erstere im Endergebnis definitiv zurückgezogen. Also tauschen wir diese beiden Elemente aus. Vergleichen Sie dann die nächsten beiden benachbarten Elemente. Auf diese Weise ist die erste Sortierrunde, bis das letzte Elementpaar verglichen wird, abgeschlossen. Es ist sicher, dass das letzte Element das größte im Array sein muss (da das relativ große auf der Rückseite jedes Mal platziert wird).
(2) Wiederholen Sie den obigen Vorgang, diesmal müssen wir nicht den letzten berücksichtigen, da er bereits angeordnet ist.
(3) Bis nur noch ein Element übrig ist, muss das Element das kleinste sein und dann kann unsere Sortierung enden. Anscheinend wurde die N-1-Sortierung durchgeführt.
Im obigen Prozess wird jedes Mal (oder "Rad" sortiert, eine Zahl langsam von einer bestimmten Position in die endgültige Position (zeichnen Sie ein schematisches Diagramm und zeichnen Sie das Array vertikal), genau wie Blasen, so dass es als "Blasensortiermethode" bezeichnet wird.
Code -Implementierung:
öffentliche Klasse Bubblesort {public static void main (String [] args) {int Score [] = {67, 69, 75, 87, 89, 90, 99, 100}; für (int i = 0; i <Score. später int temp = punkt [j]; Score [j] = Punktzahl [j + 1]; Punktzahl [j + 1] = temp; }} System.out.print ("th" + (i + 1) + "Sequenzsortierergebnis:"); für (int a = 0; a <Score.length; a ++) {System.out.print (Score [a]+"/t"); } System.out.println (""); } System.out.print ("Finale Sortierergebnis:"); für (int a = 0; a <Score.length; a ++) {System.out.print (Score [a]+"/t"); }}}
Algorithmus Leistung/Komplexität
Wir ignorieren die Zeit, in der Schleifenvariablen automatisch erhöht und initialisiert werden. Analysieren Sie zunächst die Anzahl der Vergleiche des Algorithmus. Es ist leicht zu erkennen, dass die obige Blasensortierung ohne Verbesserung in N-1-Runden unabhängig von den Eingangsdaten durchgeführt wird, und die Anzahl der Zeiten, in denen jede Sortierrunde verglichen wird, nimmt von N-1 auf 0 ab. Dann ist die Gesamtzahl der Vergleiche (n-1)+(n-2)+...+2+1 = (n-1) n/2 beschrieben (n^2). (Da ich nicht weiß, wie ich hier Quadrate herstellen kann, benutze ich hier n^2, um Quadrate darzustellen, das gleiche unten)
Schauen wir uns die Anzahl der Aufgaben an. Die hier bezieht sich hier auf den Austauschvorgang. Für den obigen Code entspricht 1 Austausch drei Zuordnungen. Da nicht jedes Mal zum Austausch erforderlich ist, hängt die Anzahl der Zuweisungsvorgänge mit den Eingabedaten zusammen. Im besten Fall beträgt die Anzahl der Zuordnungen, wenn die Reihenfolge am Anfang ist, 0. Im schlimmsten Fall beträgt die Anzahl der Zuordnungen (n-1) N/2. Unter der Annahme, dass die Eingabedaten durchschnittliche (oder "vollständig zufällige") Verteilung sind, dann etwa die Hälfte der Anzahl der Börsen. Aus den obigen Ergebnissen können wir den Durchschnittsfall erhalten, wobei die Anzahl der Zuordnungen 3/2 * (n^2)/2 = 3/4 * (n^2) beträgt.
Zusammenfassend ist in jedem Fall die Komplexität des Blasensortierraums (zusätzlicher Raum) immer o (1).
verbessern
Die optimale Zeitkomplexität wird angezeigt, wenn die Daten vollständig geordnet sind, dh o (n). In anderen Fällen ist es fast immer o (n^2). Daher funktioniert der Algorithmus am besten, wenn die Daten im Grunde genommen bestellt werden.
Wie kann der obige Code jedoch eine Komplexität von O (n) haben? Da sich das oben auf grundlegende Ideen konzentriert, ist dies nur der einfachste Fall. Damit der Algorithmus in dem besten Fall die Komplexität von O (N) aufweist, müssen einige Verbesserungen vorgenommen werden. Der verbesserte Code ist:
public static void bubblesort (int [] arr) {int temp = 0; Boolean Swap; für (int i = arr.length -1; i> 0; --i) {// Die Länge jeder Sorte muss swap = false sein; für (int j = 0; j <i; ++ j) {// vom ersten Element zum i-h-Element if (arr [j]> arr [j +1]) {temp = arr [j]; arr [j] = arr [j + 1]; arr [j + 1] = temp; Swap = wahr; }} // Schleifen j if (swap == false) {break; }} // Loop i} // Methode BubblesortDa die Blasensortierung bei großen Datenmengen kaum verwendet wird, verursachen die zusätzlichen booleschen Variablen bei der Verwendung kleiner Daten tatsächlich zusätzlichen Aufwand. Ich persönlich denke also, dass der verbesserte Algorithmus oben nur rein theoretisch ist. Normalerweise schreiben Sie einfach den vorherigen, indem Sie sprudeln.
Algorithmusstabilität
Es ist leicht zu erkennen, dass wir ihre Positionen nicht austauschen müssen, wenn benachbarte Elemente gleich sind, also ist die Blasenart eine stabile Art.
Algorithmus anwendbarer Szenarien
Die Idee der Blasensortierung ist einfach und der Code ist einfach, was besonders für die Sortierung kleiner Daten geeignet ist. Aufgrund der hohen Komplexität des Algorithmus ist es jedoch nicht für die Verwendung geeignet, wenn das Datenvolumen groß ist. Wenn Sie es verwenden müssen, wenn mehr Daten vorhanden sind, ist es am besten, den Algorithmus zu verbessern, z. B. die Auswahl der Sortiermethode.