Einfache Beispielanalyse der Blasensortierung in Java

In diesem Artikel werden hauptsächlich Java-Beispiele für die einfache Blasensortierung ausführlich vorgestellt, die einen bestimmten Referenzwert haben

Algorithmusprinzip

Vergleichen angrenzende Elemente. Wenn das erste größer als das zweite ist, tauschen Sie beide aus.

Machen Sie dasselbe für jedes Paar benachbarter Elemente, beginnend mit dem ersten Paar und endend mit dem letzten Paar. Zu diesem Zeitpunkt sollte das letzte Element die größte Zahl sein.

Wiederholen Sie die obigen Schritte für alle Elemente außer dem letzten.

Wiederholen Sie die obigen Schritte jedes Mal für immer weniger Elemente, bis keine Zahlenpaare mehr zum Vergleichen vorhanden sind.

2. Implementierungsideen

Verwenden Sie zur Implementierung eine Doppelschleife, wobei die äußere Schleifenvariable auf i und die innere Schleifenvariable auf j gesetzt ist. Wenn n Zahlen sortiert werden müssen, wird die äußere Schleife n-1 Mal und die innere Schleife n-1, n-2, ..., 1 Mal wiederholt. Die beiden verglichenen Elemente beziehen sich jedes Mal auf die innere Schleife j. Sie können durch a[j] bzw. a[j+1] identifiziert werden. Die Werte von i sind 1, 2, ..., n-1 . Für jedes i ist der Wert von j 0,1,2,...n-i.

Angenommen, die Array-Länge ist N:

1. Vergleichen Sie die beiden benachbarten Daten vorher und nachher. Wenn die ersteren Daten größer sind als die letzteren Daten, werden die beiden Daten ausgetauscht.
2． Auf diese Weise „sinken“ die größten Daten nach dem Durchlaufen der 0. Daten zu den N-1. Daten des Arrays zur N-1. Position des Arrays.
3. N = N-1, wenn N nicht 0 ist, wiederholen Sie die beiden vorherigen Schritte, andernfalls ist die Sortierung abgeschlossen.

3. Code-Implementierung

package sort;
import java.util.Arrays;
/**
 * 冒泡排序
 * 比较相邻的元素。如果第一个比第二个大，就交换他们两个。
 * 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。
 * 针对所有的元素重复以上的步骤，除了最后一个。
 * 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
 */

public class BubbleSort {
  public static void bubbleSort(int[] arr) {
    boolean flag=true;
    while (flag) {
      flag=false;
      int temp = 0;
      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]) {   //交换两数位置
            temp = arr[j];
            arr[j] = arr[j + 1];
            arr[j + 1] = temp;
            flag=true;
          }
        }
        if (!flag){
          break;
        }
        }
      }
    }
  public static void main(String[] args){
    int a[]=new int[]{345,22,43,12,65,335,124,636,3};
    BubbleSort.bubbleSort(a);
    System.out.print(Arrays.toString(a));
  }
}

4. Leistungsanalyse

Wenn der Anfangszustand der Datensatzsequenz „positive Reihenfolge“ ist, muss der Blasensortierungsprozess nur eine Sortierung durchführen, und während des Sortiervorgangs sind nur n-1 Vergleiche erforderlich, ohne dass die Datensätze umgekehrt verschoben werden die Datensatzreihenfolge Für die „umgekehrte Reihenfolge“ sind n (n-1)/2 Vergleiche und Datensatzverschiebungen erforderlich. Daher beträgt die Gesamtzeitkomplexität der Blasensortierung O(n*n).

5. Algorithmusoptimierung

Die Mängel und Verbesserungsmethoden der Blasensortiermethode:

Erstens während des Sortiervorgangs, nach der Ausführung des letzten Obwohl die Daten nach dem Sortieren vollständig sortiert wurden, kann das Programm nicht feststellen, ob die Sortierung abgeschlossen ist. Um dieses Problem zu lösen, kann ein Flag gesetzt und sein Anfangswert auf true gesetzt werden, was anzeigt, dass die sortierte Tabelle ungeordnet ist Tabelle, setzen Sie den Flag-Wert auf true, bevor jede Sortierung beginnt, und ändern Sie das Flag während des Datenaustauschs auf false. Überprüfen Sie zu Beginn einer neuen Sortierrunde dieses Flag. Wenn dieses Flag falsch ist, bedeutet dies, dass beim letzten Mal kein Datenaustausch stattgefunden hat. Andernfalls wird die Sortierung durchgeführt >Zweitens gibt es bei der Blasensortierung möglicherweise keinen Datenaustausch in einem Scan, oder es gibt einen oder mehrere Datenaustausche. Beim herkömmlichen Blasensortierungsalgorithmus und einigen in den letzten Jahren verbesserten Algorithmen werden nur Informationen darüber ausgetauscht, ob Daten ausgetauscht werden In einem Scan werden die Daten aufgezeichnet und die Standortinformationen, an denen der Austausch stattfindet, werden nicht verarbeitet. Um diese Informationen vollständig zu nutzen, kann für jedes Datenpaar in umgekehrter Reihenfolge in einem globalen Scan eine lokale Blasensortierung durchgeführt werden, die als lokale Blasensortierung bezeichnet wird. Die lokale Blasensortierung hat die gleiche zeitliche Komplexität wie der Blasensortierungsalgorithmus, und die Anzahl der Vergleiche und Verschiebungen der erforderlichen Schlüsselwörter ist sowohl in Vorwärts- als auch in Rückwärtsreihenfolge genau gleich. Da die Anzahl der Datenbewegungen zwischen der lokalen Blasensortierung und der Blasensortierung immer gleich ist und die Anzahl der für die lokale Blasensortierung erforderlichen Schlüsselwortvergleiche oft geringer ist als die der Blasensortierung, bedeutet dies, dass die lokale Blasensortierung wahrscheinlich eine hat Die geringere durchschnittliche Anzahl von Vergleichen wurde verbessert, wenn der Vorteil weniger Vergleiche nicht ausreicht, um den durch die Komplexität des Programms verursachten zusätzlichen Aufwand auszugleichen, und wenn die Datenmenge groß ist deutlich besser als die Blasensorte. Wenn wir für N ungeordnete Daten eine Blasensortierung durchführen und die k-ten Daten und die k+1-ten Daten in umgekehrter Reihenfolge sind, wird eine vorwärts gerichtete Blasensortierung für die k+1-ten Daten durchgeführt, sodass Move Bringen Sie es in die entsprechende Position, dh passen Sie die vorherigen k + 1-Daten an die positive Sequenz an. Da diese Bubbling-Methode nur die ersten k+1 Daten in Bubblings umwandelt, nennen wir sie lokales Bubbling

Das obige ist der detaillierte Inhalt vonEinfache Beispielanalyse der Blasensortierung in Java. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!