Prinzip: Vergleichen Sie zwei benachbarte Elemente und Austauschelemente mit großen Werten am rechten Ende.
Idee: Vergleichen Sie zwei benachbarte Zahlen nacheinander und legen Sie die Dezimalstellen vor und die großen Zahlen in die Rückseite. Das heißt, bei der ersten Reise: Vergleichen Sie zuerst die erste und zweite Zahlen, geben Sie die Dezimalzahl vor und die großen Zahlen danach. Vergleichen Sie dann die zweite Zahl und die dritte Zahl, setzen Sie die Dezimalzahl vor und nach der großen Zahl so fort, bis die letzten beiden Zahlen verglichen werden, und stellen Sie die Dezimalzahl vor und nach der großen Zahl. Wiederholen Sie den ersten Schritt, bis alle Sortierungen abgeschlossen sind.
Zum Beispiel: Um das Array zu sortieren: int [] arr = {6,3,8,2,9,1};
Erste Ordnung:
Erste Sorte: 6 und 3 Vergleichen, 6 ist größer als 3, Swap -Position: 368291
Zweite Sorte: 6 und 8 Vergleichen, 6 ist weniger als 8, keine Austauschposition: 368291
Die dritte Ordnung: 8 und 2 vergleichen, 8 ist größer als 2, Swap -Position: 362891
Vierte Ordnung: 8 und 9 Vergleich, 8 ist weniger als 9, keine Austauschposition: 362891
Fünfte Ordnung: 9 und 1 Vergleich: 9 ist größer als 1, Swap -Position: 362819
Die erste Reise wurde insgesamt 5 -mal verglichen, Sortierergebnisse: 362819
---------------------------------------------------------------------
Zweite Ordnung:
Erste Sortierung: 3 und 6 Vergleich, 3 ist weniger als 6, keine Austauschposition: 362819
Zweite Sorte: 6 und 2 Vergleich, 6 ist größer als 2, Swap -Position: 326819
Die dritte Ordnung: 6 und 8 vergleichen, 6 ist größer als 8, keine Austauschposition: 326819
Vierte Ordnung: 8 und 1 Vergleich, 8 ist größer als 1, Swap -Position: 326189
Die zweite Reise wurde insgesamt verglichen und das Sortierergebnis war: 326189
---------------------------------------------------------------------
Die dritte Ordnung:
Erste Sorte: 3 und 2 Vergleich, 3 ist größer als 2, Swap -Position: 236189
Zweite Sorte: 3 und 6 Vergleich, 3 ist weniger als 6, keine Austauschposition: 236189
Die dritte Ordnung: 6 und 1 vergleichen, 6 ist größer als 1, Swap -Position: 231689
Die zweite Reise wurde insgesamt verglichen, und das Sortierergebnis war: 231689
---------------------------------------------------------------------
Die vierte Ordnung:
Erste Sortierung: 2 und 3 Vergleich, 2 ist weniger als 3, keine Austauschposition: 231689
Zweite Sorte: 3 und 1 Vergleich, 3 ist größer als 1, Swap -Position: 213689
Die zweite Reise wurde insgesamt verglichen, und das Sortierergebnis war: 213689
---------------------------------------------------------------------
Die fünfte Ordnung:
Erste Sorte: 2 und 1 Vergleich, 2 ist größer als 1, Swap -Position: 123689
Die zweite Reise wurde insgesamt verglichen, und das Sortierergebnis war: 123689
---------------------------------------------------------------------
Endergebnis: 123689
---------------------------------------------------------------------
Daraus können wir erkennen, dass N-Zahlen sortiert werden müssen und die N-1-Zeiten insgesamt sortiert werden. Die Anzahl der Sortierzeiten für jeden I-Pass ist (NI), sodass Sie eine Doppelschleifungsaussage verwenden können, um zu steuern, wie oft die äußere Schicht die Anzahl der Male für jede Reise steuert, dh,,
für (int i = 1; i <arr.length-1; i ++) {für (int j = 1; j <arr.length-i; j ++) {// Swap-Position}}Vorteile der Blasensortierung: Jedes Mal, wenn Sie sortieren, vergleichen Sie weniger, denn jedes Mal, wenn Sie sortieren, finden Sie einen größeren Wert. Wie oben erwähnt: Nach dem ersten Vergleich muss die letzte Zahl die größte Zahl sein. Wenn Sie das zweite Mal sortieren, müssen Sie nur andere Zahlen als die letzte Zahl vergleichen, und Sie können auch feststellen, dass die größte Zahl nach der Anzahl der am zweiten Vergleich eingestuft wird. Wenn Sie das dritte Mal vergleichen, müssen Sie nur andere Zahlen als die letzten beiden Zahlen vergleichen, und so weiter ... mit anderen Worten, wenn Sie keinen Vergleich durchführen, jedes Mal, wenn Sie einmal vergleichen, reduziert Sie die Menge des Algorithmus in gewissem Maße.
In Bezug auf die Zeitkomplexität:
1. Wenn unsere Daten in Ordnung sind, müssen wir nur eine Reise unternehmen, um die Sortierung abzuschließen. Die erforderliche Anzahl von Vergleiche und Datensatzbewegungen ist beide der Mindestwert, dh: cmin = n-1; Mmin = 0; Daher ist die beste Zeitkomplexität für die Blasensortierung o (n).
2. Wenn unsere Daten leider umgekehrt sind, ist eine N-1-Bestellung erforderlich. Jede Ordnung muss verglichen werden (1 ≤ i ≤ N-1), und jeder Vergleich muss dreimal in den Datensatz verschoben werden, um die Exchange-Datensatzposition zu erreichen. In diesem Fall erreichen die Vergleichs- und Bewegungszeiten sowohl das Maximum: die schlimmste Zeitkomplexität der Blasensorte: O (N2).
Zusammenfassend: Die Gesamtdurchschnittszeitkomplexität der Blasensorte lautet: O (N2).
Code -Implementierung:
/ * * Bubble sortiert */öffentliche Klasse Bubblesort {public static void main (String [] args) {int [] arr = {6,3,8,2,9,1}; System.out.println ("Das Array vor der Sortierung ist:"); für (int num: arr) {System.out.print (num+""); } für (int i = 1; i <arr.length; i ++) {// Die äußere Schleife steuert die Anzahl der Sortierzeiten für (int j = 1; j <arr.length-i; j ++) {// Die innere Schleife steuert, wie oft es jedes Mal sortiert ist (arr [j-1]> arr [j] {int temp = arr [j] [j] [j] [j]; arr [j] = arr [j-1]; arr [j-1] = temp; }}} System.out.println (); System.out.println ("Das sortierte Array ist:"); für (int num: arr) {System.out.print (num+""); }}}