Originaltitel: Klassischer Algorithmus in Java: Bubble Sort (Bubble Sort)
Was ist Bubble Sort?
Bubble Sort ist ein einfacher Sortieralgorithmus, der Elemente basierend auf der Reihenfolge paarweise miteinander vergleicht. Wenn die Reihenfolge von groß nach klein ist, wird beim Vergleich zweier Elemente das größere zuerst eingestuft, andernfalls wird das größere später eingestuft. Die Blasensortierung wird in die Sortierung von groß nach klein und die Sortierung von klein nach groß unterteilt.
Prinzip: Vergleichen Sie zwei benachbarte Elemente und tauschen Sie das Element mit dem größeren Wert am rechten Ende aus.
Idee: Vergleichen Sie nacheinander zwei benachbarte Zahlen, setzen Sie die Dezimalzahl voran und die große Zahl hinten. Das heißt, im ersten Durchgang: Vergleichen Sie zunächst die erste und die zweite Zahl, setzen Sie die Dezimalzahlen voran und die großen Zahlen hinten. Vergleichen Sie dann die zweite und die dritte Zahl, setzen Sie die Dezimalzahl voran und die große Zahl hinten und machen Sie so weiter, bis Sie die letzten beiden Zahlen vergleichen, stellen Sie die Dezimalstelle voran und die große Zahl hinten. Wiederholen Sie den ersten Schritt, bis die Sortierung abgeschlossen ist.
Beispiel: So sortieren Sie das Array: int[] arr={6,3,8,2,9,1};
Erste Sortierung:
Erste Sortierung: 6 und 3 Vergleich, 6 ist größer als 3, Positionen tauschen: 3 6 8 2 9 1
Zweite Sortierung : 6 und 8 werden verglichen, 6 ist kleiner als 8, kein Positionstausch: 3 6 8 2 9 1
Die dritte Sortierung: 8 und 2 werden verglichen, 8 ist größer als 2 , Austauschposition: 3 6 2 8 9 1
Die vierte Ordnung: 8 und 9Vergleich, 8 ist kleiner als 9, kein Positionstausch: 3 6 2 8 9 1
Die fünfte Sortierung: 9 und 1 Vergleich: 9 ist größer als 1, Positionen tauschen: 3 6 2 8 1 9
Insgesamt wurden bei der ersten Fahrt 5 Vergleiche durchgeführt und die Sortierergebnisse waren: 3 6 2 8 1 9
--------------------------------- --- ---------
Zweite Sortierung:
Erste Sortierung: 3 und 6 im Vergleich ist 3 kleiner als 6 , Positionen nicht vertauschen: 3 6 2 8 1 9
Die zweite Sortierung: 6 und 2 Vergleich, 6 ist größer als 2, Positionen tauschen: 3 2 6 8 1 9
Die dritte Rangliste: 6 und 8 Vergleichen Sie, 6 ist größer als 8, ohne Positionstausch: 3 2 6 8 1 9
Die vierte Sortierung: 8 und 1 Vergleich, 8 ist größer als 1, Positionen tauschen: 3 2 6 1 8 9
Im zweiten Durchgang wurden insgesamt 4 Vergleiche durchgeführt, und die Sortierergebnisse waren: 3 2 6 1 8 9
---- --------------------------------------- ----------- ---------------
Die dritte Sortierung:
Die erste Sortierung: 3 Im Vergleich zu 2 ist 3 größer als 2, Positionen tauschen: 2 3 6 1 8 9
Zweite Sortierung: 3 und 6 Vergleichen Sie, 3 ist kleiner als 6, Positionen nicht tauschen: 2 3 6 1 8 9
Die dritte Sortierung: 6 und 1 Vergleich, 6 Größer als 1, Positionen tauschen: 2 3 1 6 8 9
Die zweite Fahrt wird durchgeführt insgesamt 3 Vergleiche, Sortierergebnisse: 2 3 1 6 8 9
----------- - ------------------------------------------------- - -------
Die vierte Sortierung:
Die erste Sortierung: 2 und 3 Vergleich, 2 ist kleiner als 3, kein Positionstausch: 2 3 1 6 8 9
Zweite Sortierung: 3 und 1 Vergleich , 3 ist größer als 1, Positionen tauschen: 2 1 3 6 8 9
Bei der zweiten Fahrt wurden insgesamt 2 Vergleiche durchgeführt, Sortierergebnisse: 2 1 3 6 8 9
------------------------------ --- -------
Fünfte Sortierung:
Erste Sortierung: 2 und 1 werden verglichen, 2 ist größer als 1, Tauschpositionen: 1 2 3 6 8 9
Die zweite Fahrt wurde insgesamt 1mal vergleichen, Ergebnisse sortieren: 1 2 3 6 8 9
--------------------------------- ---------- -------------------------- --------
Endergebnis:1 2 3 6 8 9
------ ----------- ------------------------- -----------
Es ist ersichtlich, dass: N Zahlen sortiert werden müssen und insgesamt N-1 Sortierung wird jedes Mal durchgeführt. Die Anzahl der Sortiervorgänge für i beträgt (N-i) Mal, sodass Sie eine Doppelschleifenanweisung verwenden können. Die äußere Ebene steuert, wie oft die Schleife ausgeführt wird, und die innere Ebene steuert, wie oft die Schleife ausgeführt wird. Die Ebene steuert die Anzahl der Schleifen für jeden Durchgang, d. h.
for(int i=1;i<arr.length;i++){
for(int j=1;j<arr.length-i;j++){
//交换位置
}Nach dem Login kopieren
Vorteile der Blasensortierung: Jedes Mal, wenn eine Sortierung durchgeführt wird, gibt es einen Vergleich weniger, da jedes Mal, wenn a pass wird durchgeführt. Beim Sortieren wird immer ein größerer Wert gefunden. Wie im obigen Beispiel: Nach dem ersten Vergleich muss die letzte Zahl die größte Zahl sein. Bei der zweiten Sortierung müssen nur andere Zahlen außer der letzten Zahl verglichen werden, und Sie können auch die größte Zahl finden hinter den Zahlen, die am zweiten Vergleich teilnehmen, müssen beim dritten Vergleich nur die anderen Zahlen außer den letzten beiden Zahlen verglichen werden, und so weiter... Mit anderen Worten, ohne Vergleich, jedes Mal Ein Vergleich weniger pro Fahrt verringert sich die Menge des Algorithmus bis zu einem gewissen Grad.
In Bezug auf die zeitliche Komplexität:
1. Wenn unsere Daten in Ordnung sind, benötigen wir nur eine Fahrt, um die Sortierung abzuschließen. Die erforderliche Anzahl der Vergleiche und die Anzahl der Datensatzbewegungen erreichen beide den Mindestwert, das heißt: Cmin=n-1; Mmin=0; deshalb, sprudelnd Die beste Zeitkomplexität der Sortierung ist O(n).
2. Wenn unsere Daten leider in umgekehrter Reihenfolge vorliegen, sind n-1 Durchgänge erforderlich. Jeder Sortiervorgang erfordert n-i Vergleiche (1≤i≤n-1), und jeder Vergleich muss den Datensatz dreimal verschieben, um die Position des Austauschdatensatzes zu erreichen. In diesem Fall erreicht die Anzahl der Vergleiche und Bewegungen das Maximum: 
Die schlechteste Zeitkomplexität der Blasensortierung ist: O(n2).
Zusammenfassend: Die gesamte durchschnittliche Zeitkomplexität der Blasensortierung beträgt: O(n2 ).
Blasensortierungscode für den klassischen Java-Algorithmus :
/*
* 冒泡排序 */public class BubbleSort {
public static void main(String[] args) {
int[] arr={6,3,8,2,9,1};
System.out.println("排序前数组为：");
for(int num:arr){
System.out.print(num+" ");
}
for(int i=0;i<arr.length-1;i++){//外层循环控制排序趟数 for(int j=0;j<arr.length-1-i;j++){//内层循环控制每一趟排序多少次 if(arr[j]>arr[j+1]){
int temp=arr[j];
arr[j]=arr[j+1];
arr[j+1]=temp;
}
}
}
System.out.println();
System.out.println("排序后的数组为：");
for(int num:arr){
System.out.print(num+" ");
}
}
}Nach dem Login kopieren
Für Weitere Informationen zum Blasensortieren mit dem klassischen Java-Algorithmus finden Sie auf der chinesischen PHP-Website!
