Einige gängige Java-Blasensortieralgorithmen: Sortieren in aufsteigender Reihenfolge

Java-Blasensortierung: Mehrere gängige Schreibmethoden von klein bis groß, es werden spezifische Codebeispiele benötigt.

Die Blasensortierung ist ein einfacher Sortieralgorithmus, der zwei benachbarte Elemente wiederholt vergleicht und sie nach Größe sortiert. Es werden Vertauschungen durchgeführt, bis die gesamte Sequenz erreicht ist ist in Ordnung. In Java gibt es mehrere gängige Schreibmethoden und Optimierungsmethoden für die Blasensortierung. Im Folgenden werden fünf gängige Schreibmethoden vorgestellt und spezifische Codebeispiele bereitgestellt.

Die erste Schreibweise: Gewöhnliche Blasensortierung

Gewöhnliche Blasensortierung verschachtelt direkt zwei Schleifenebenen. Die äußere Schleife steuert die Anzahl der Vergleichsrunden, und die innere Schleife führt spezifische Vergleiche und Austausche durch.

public static void bubbleSort1(int[] arr) {
    int n = arr.length;
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - 1 - i; j++) {
            if (arr[j] > arr[j+1]) {
                int temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
            }
        }
    }
}

Die zweite Schreibweise: Optimierung der äußeren Schleife

Wenn in einer Sortierrunde kein Austausch durchgeführt wird, bedeutet dies, dass das Array bereits in Ordnung ist und die Sortierung vorzeitig beendet werden kann . Um diese Optimierung zu erreichen, können wir ein Flag-Bit hinzufügen, um aufzuzeichnen, ob ein Austausch durchgeführt wurde.

public static void bubbleSort2(int[] arr) {
    int n = arr.length;
    boolean swapped;
    for (int i = 0; i < n - 1; i++) {
        swapped = false;
        for (int j = 0; j < n - 1 - i; 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;
        }
    }
}

Die dritte Schreibweise: Optimierung der inneren Schleife

Basierend auf der zweiten Schreibweise können Sie feststellen, dass jede Vergleichsrunde das größte Element bis zum Ende „aufbläht“. Daher kann die Anzahl der Innenschleifenvergleiche pro Runde schrittweise reduziert werden.

public static void bubbleSort3(int[] arr) {
    int n = arr.length;
    int lastSwapIndex;
    for (int i = 0; i < n - 1; i++) {
        lastSwapIndex = 0;
        for (int j = 0; j < n - 1 - i; j++) {
            if (arr[j] > arr[j+1]) {
                int temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
                lastSwapIndex = j + 1;
            }
        }
        i = n - lastSwapIndex - 2;
    }
}

Die vierte Schreibweise: Optimierung der inneren und äußeren Schleife

Wenn sich das Array in einer bestimmten Vergleichsrunde nicht austauscht, bedeutet dies laut der dritten Schreibweise, dass die Elemente hinter dem Array bereits in Ordnung sind , und die Sortierung kann vorzeitig beendet werden.

public static void bubbleSort4(int[] arr) {
    int n = arr.length;
    int lastSwapIndex, rightBoundary;
    rightBoundary = n - 1;
    for (int i = 0; i < n - 1; i++) {
        lastSwapIndex = 0;
        for (int j = 0; j < rightBoundary; j++) {
            if (arr[j] > arr[j+1]) {
                int temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
                lastSwapIndex = j + 1;
            }
        }
        rightBoundary = lastSwapIndex;
        if (rightBoundary <= 1) {
            break;
        }
    }
}

Die fünfte Schreibweise: Optimierung der äußeren Schleife und der inneren Schleife

Basierend auf der vierten Schreibweise können wir feststellen, dass in jeder Vergleichsrunde das größte Element der aktuellen Runde gefunden und in die richtige Position gebracht wird Position. Daher können wir in jeder Vergleichsrunde sowohl den Maximal- als auch den Minimalwert ermitteln und sortieren.

public static void bubbleSort5(int[] arr) {
    int n = arr.length;
    int lastSwapIndex, leftBoundary, rightBoundary;
    leftBoundary = 0;
    rightBoundary = n - 1;
    while (leftBoundary < rightBoundary) {
        lastSwapIndex = 0;
        for (int j = leftBoundary; j < rightBoundary; j++) {
            if (arr[j] > arr[j+1]) {
                int temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
                lastSwapIndex = j + 1;
            }
        }
        rightBoundary = lastSwapIndex;
        for (int j = rightBoundary; j > leftBoundary; j--) {
            if (arr[j] < arr[j-1]) {
                int temp = arr[j];
                arr[j] = arr[j-1];
                arr[j-1] = temp;
                lastSwapIndex = j - 1;
            }
        }
        leftBoundary = lastSwapIndex;
    }
}

Die oben genannten fünf gängigen Methoden zum Schreiben von Blasen. Für jede Schreibmethode gibt es unterschiedliche Optimierungsmethoden. Bei der tatsächlichen Verwendung können Sie die geeignete Schreibmethode entsprechend der jeweiligen Situation auswählen. Durch diese Optimierungen kann die Effizienz der Blasensortierung verbessert und die Sortierzeit verkürzt werden.

Obwohl die Blasensortierung einfach ist, ist ihre Leistung beim Sortieren großer Datenmengen schlecht. Daher werden in praktischen Anwendungen häufiger effizientere Sortieralgorithmen wie Schnellsortierung, Zusammenführungssortierung usw. verwendet.

Das obige ist der detaillierte Inhalt vonEinige gängige Java-Blasensortieralgorithmen: Sortieren in aufsteigender Reihenfolge. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!