Java-Implementierung des Blasensortierungsalgorithmus und sein einfaches Optimierungsbeispiel

Prinzip

Bubble Sort ist wahrscheinlich ein Algorithmus, den alle Programmierer verwenden werden, und es ist auch einer der bekanntesten Algorithmen.
Die Idee ist nicht kompliziert:
Angenommen, wir wollen jetzt das Array arr[] sortieren, das n Elemente hat.
1. Wenn n=1: Es besteht offensichtlich keine Notwendigkeit, eine Vereinbarung zu treffen. (Eigentlich scheint diese Diskussion unnötig)
2. Wenn n>1:
(1) Wir beginnen mit dem ersten Element und vergleichen alle zwei benachbarten Elemente. Wenn das vorherige Element besser ist als das folgende Element, dann Ersterer wird im Endergebnis definitiv zurückliegen. Also vertauschen wir diese beiden Elemente. Vergleichen Sie dann die nächsten beiden benachbarten Elemente. Dies wird fortgesetzt, bis das letzte Elementpaar verglichen und die erste Sortierrunde abgeschlossen ist. Sie können sicher sein, dass das letzte Element das größte im Array sein muss (da das relativ große immer hinten platziert wird).
(2) Wiederholen Sie den obigen Vorgang. Diesmal müssen wir den letzten Schritt nicht berücksichtigen, da er bereits festgelegt ist.
(3) Dies wird so lange durchgeführt, bis nur noch ein Element übrig ist. Dieses Element muss das kleinste sein, dann kann unsere Sortierung abgeschlossen werden. Offensichtlich findet eine n-1-Sortierung statt.
Im obigen Prozess „schwebt“ bei jeder (oder „runden“) Sortierung eine Zahl langsam von einer bestimmten Position zur endgültigen Position (zeichnen Sie ein schematisches Diagramm und zeichnen Sie das Array vertikal, um es anzuzeigen). genau wie Blasen, daher nennt man es „Blasensortierung“.

Code-Implementierung:

public class BubbleSort{
   public static void main(String[] args){
     int score[] = {67, 69, 75, 87, 89, 90, 99, 100};
     for (int i = 0; i < score.length -1; i++){  //最多做n-1趟排序
       for(int j = 0 ;j < score.length - i - 1; j++){  //对当前无序区间score[0......length-i-1]进行排序(j的范围很关键，这个范围实在逐步缩小的)
         if(score[j] < score[j + 1]){  //把小的值交换到后面
           int temp = score[j];
           score[j] = score[j + 1];
           score[j + 1] = temp;
         }
       }      
       System.out.print("第" + (i + 1) + "次排序结果：");
       for(int a = 0; a < score.length; a++){
         System.out.print(score[a] + "\t");
       }
       System.out.println("");
     }
       System.out.print("最终排序结果：");
       for(int a = 0; a < score.length; a++){
         System.out.print(score[a] + "\t");
     }
   }
 }

Algorithmusleistung/-komplexität
Wir ignorieren die Zeit für die Inkrementierung und Initialisierung der Schleifenvariablen. Analysieren Sie zunächst die Anzahl der Vergleiche des Algorithmus. Es ist leicht zu erkennen, dass die obige Blasensortierung ohne jede Verbesserung unabhängig von den Eingabedaten n-1 Sortierrunden durchführt und die Anzahl der für jede Sortierrunde erforderlichen Vergleiche von n-1 auf 0 sinkt. Dann beträgt die Gesamtzahl der Vergleiche (n-1)+(n-2)+...+2+1 = (n-1)n/2≈(n^2)/2. (Da ich hier nicht weiß, wie ich das Quadrat berechnen soll, verwende ich hier n^2, um das Quadrat darzustellen, dasselbe unten)
Schauen wir uns die Anzahl der Aufgaben an. Die Zuweisung bezieht sich hier auf den Austauschvorgang. Für den obigen Code entspricht ein Austausch drei Zuweisungen. Da ein Austausch nicht jedes Mal erforderlich ist, hängt die Anzahl der Zuweisungsvorgänge von den Eingabedaten ab. Im besten Fall, also bei der Bestellung von Anfang an, beträgt die Anzahl der Zuweisungen 0. Im schlimmsten Fall beträgt die Anzahl der Zuweisungen (n-1)n/2. Unter der Annahme, dass die Eingabedaten gleichmäßig (oder „völlig zufällig“) verteilt sind, gibt es etwa halb so viele Vertauschungen wie Vergleiche. Aus den obigen Ergebnissen können wir ableiten, dass im Durchschnitt die Anzahl der Zuweisungen 3/2 * (n^2)/2 = 3/4*(n^2) beträgt.
Um es zusammenzufassen: Egal In diesem Fall beträgt die Raumkomplexität (zusätzlicher Raum) der Blasensortierung immer O (1).

Verbesserung
zeigt die optimale Zeitkomplexität, die O(n) ist, wenn die Daten vollständig geordnet sind. Ansonsten ist es fast immer O(n^2). Daher ist die Leistung des Algorithmus am besten, wenn die Daten grundsätzlich geordnet sind.
Wie kann der obige Code jedoch eine O(n)-Komplexität haben? Da sich das Obige auf die Grundidee konzentriert, handelt es sich tatsächlich nur um den einfachsten Fall, damit der Algorithmus im besten Fall eine O(n)-Komplexität aufweist. Der verbesserte Code ist:

public static void bubbleSort(int[] arr) {
  int temp = 0;
  boolean swap;
  for (int i = arr.length - 1; i > 0; --i) { // 每次需要排序的长度
    swap=false;
    for (int j = 0; j < i; ++j) { // 从第一个元素到第i个元素
      if (arr[j] > arr[j + 1]) {
        temp = arr[j];
        arr[j] = arr[j + 1];
        arr[j + 1] = temp;
        swap=true;
      }
    }//loop j
    if (swap==false){
      break;
    }
  }//loop i
}// method bubbleSort

Da die Blasensortierung bei der Verwendung großer Datenmengen fast nie verwendet wird, verursacht das Hinzufügen boolescher Variablen bei der Verwendung kleiner Datenmengen zusätzlichen Aufwand. Daher denke ich persönlich, dass der oben genannte verbesserte Algorithmus rein theoretisch ist. Normalerweise schreibe ich für die Blasensortierung einfach den ersteren.

Algorithmusstabilität
Es ist leicht zu erkennen, dass wir ihre Positionen nicht austauschen müssen, wenn benachbarte Elemente gleich sind, sodass die Blasensortierung eine stabile Sortierung ist.

Anwendbare Szenarien für den Algorithmus
Die Blasensortierung hat eine einfache Idee und einen einfachen Code, der sich besonders zum Sortieren kleiner Datenmengen eignet. Aufgrund der hohen Komplexität des Algorithmus ist er jedoch nicht für den Einsatz bei großen Datenmengen geeignet. Wenn es bei großen Datenmengen verwendet werden muss, ist es am besten, den Algorithmus zu verbessern, z. B. die Auswahlsortierung.

Weitere Java-Implementierungen des Blasensortierungsalgorithmus und seine einfachen Optimierungsbeispiele finden Sie auf der chinesischen PHP-Website!