Den Bubble-Sort-Algorithmus verstehen (mit Beispielen in Java)

Detaillierte Erklärung von Bubble Sort: ein einfacher Sortieralgorithmus

Bubble Sort ist einer der einfachsten Sortieralgorithmen. Dabei werden benachbarte Elemente wiederholt verglichen und ausgetauscht, wenn sie nicht in der richtigen Reihenfolge sind. Wenn die Sortierreihenfolge beispielsweise aufsteigend ist, werden benachbarte Elemente verglichen und das größere Element wird rechts platziert. In jeder Iteration vergleichen wir nur die unsortierten Elemente und platzieren das größte Element an der letzten Position der unsortierten Elemente im Array.

Dieser Algorithmus wird treffend als Blasensortierung bezeichnet, da sich die Elemente bei jeder Iteration zur rechten Seite des Arrays bewegen, wie eine Blase, die an die Wasseroberfläche steigt.

So funktioniert die Blasensortierung

Angenommen, wir möchten dieses Array in aufsteigender Reihenfolge sortieren:

Erste Iteration

In der ersten Iteration versuchen wir, das größte Element an das Ende des Arrays zu verschieben. Daher vergleichen wir wiederholt benachbarte Elemente und tauschen sie aus, wenn sie nicht in der richtigen Reihenfolge sind.

Elemente, die an die richtige Position verschoben wurden, gelten als sortiert.

Folgende Iterationen

Dieser Vorgang wird für alle Iterationen wiederholt, bis das Array sortiert ist. In jeder Iteration vergleichen wir nur die unsortierten Elemente, da die sortierten Elemente bereits in der richtigen Reihenfolge vorliegen.

Wir durchlaufen das Array n-1 Mal, wobei n die Länge des Arrays ist. Das heißt, da unser Array sechs Elemente hat, durchlaufen wir das Array nur fünfmal. Dies liegt daran, dass nach der fünften Iteration die fünf Elemente an ihren korrekten Positionen platziert wurden, sodass das letzte unsortierte Element als sortiert gilt. Nachdem alle Iterationen abgeschlossen sind, erhalten wir ein sortiertes Array.

Implementierung der Blasensortierung

public class BubbleSortTest {
    public static void main(String[] args) {
        int[] arr = {8, 2, 6, 4, 9, 1};
        System.out.println("未排序数组: " + Arrays.toString(arr));
        bubbleSort(arr);
        System.out.println("已排序数组: " + Arrays.toString(arr));
    }

    public static void bubbleSort(int[] arr) {
        int size = arr.length;

        // 循环遍历数组 size-1 次
        for (int i = 0; i < size - 1; i++) {
            // 比较相邻元素
            for (int j = 0; j < size - i - 1; j++) {
                if (arr[j] > arr[j + 1]) {
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
        }
    }
}

Durch Ausführen dieses Codes wird die folgende Ausgabe in der Konsole ausgegeben:

<code>未排序数组: [8, 2, 6, 4, 9, 1]
已排序数组: [1, 2, 4, 6, 8, 9]</code>

In dieser Implementierung der Blasensortierung durchlaufen wir jedes Mal das Array, auch wenn das Array bereits sortiert ist. Wir können den Code weiter optimieren, sodass die Sortierung stoppt, sobald das Array sortiert wurde.

Optimierte Blasensortierung

public static void bubbleSortOptimised(int[] arr){
    int size = arr.length;
    boolean swapped;

    // 循环遍历数组 size-1 次
    for (int i = 0; i < size - 1; i++) {
        swapped = false;
        // 比较相邻元素
        for (int j = 0; j < size - i - 1; j++) {
            if (arr[j] > arr[j+1]){
                int temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;

                swapped = true;
            }
        }

        // 如果没有交换，则数组已排序
        if(!swapped) break;
    }
}

Wenn wir mit dieser Implementierung versuchen, ein bereits sortiertes Array zu sortieren, iterieren wir nur einmal und stoppen, wenn keine Sortierung erfolgt.

Komplexität der Blasensortierung

Zeitliche Komplexität:

Bester Fall (O(n)):

Im besten Fall ist das Eingabearray bereits sortiert. Der Algorithmus iteriert das Array nur einmal, um zu prüfen, ob es sortiert ist, und führt keine Vertauschung durch.

Durchschnittsfall (O(n²)):

Wenn die Elemente des Eingabearrays in zufälliger Reihenfolge vorliegen. Der Algorithmus muss mehrmals iterieren und Swaps durchführen, um das Array zu sortieren.

Worst Case (O(n²)):

Das schlimmste Szenario ist, dass das Eingabearray in umgekehrter Reihenfolge sortiert wird. Der Algorithmus durchläuft n-1 Iterationen und führt die maximale Anzahl an Swaps durch.

Raumkomplexität O(1):

Bubble Sort ist ein In-Place-Sortieralgorithmus, das heißt, es erfordert keinen zusätzlichen Speicher proportional zur Größe des Eingabearrays.

Fazit

Bubble Sort ist ein Algorithmus, der leicht zu verstehen und zu implementieren ist. Aufgrund seiner hohen zeitlichen Komplexität ist es jedoch nicht für die Verarbeitung großer Datenmengen geeignet. Die Blasensortierung kann verwendet werden, wenn Sie mit kleinen Datensätzen arbeiten oder wenn Ihnen die Komplexität egal ist.

Das obige ist der detaillierte Inhalt vonDen Bubble-Sort-Algorithmus verstehen (mit Beispielen in Java). Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!