Detaillierte Einführung in die Java-Blasensortierung (Codebeispiel)

Der Inhalt dieses Artikels ist eine detaillierte Einführung (Codebeispiel) zur Java-Blasensortierung. Ich hoffe, dass er für Sie hilfreich ist. hat geholfen.

1. Einleitung

Da dies der erste Artikel in der Sortieralgorithmus-Reihe ist, werde ich noch ein paar Worte sagen.

Sortieren ist einer der am häufigsten verwendeten Algorithmen, z. B. die Arrays.sort()-Methode von Java. Mit dieser Methode können wir sie direkt aufrufen, ohne uns um das Innere zu kümmern Implementierungsdetails werden auch häufig in der tatsächlichen Softwareentwicklung verwendet. Aber aus der Sicht eines Entwicklers muss man wissen, warum, um zu wissen, was passiert. Durch das Üben weiterer Sortieralgorithmen erfahren wir nicht nur die zugrunde liegenden Implementierungsdetails einiger Sortiermethoden, sondern trainieren auch unser Denken und verbessern unsere Programmierfähigkeiten. Viele technische Vorstellungsgespräche beinhalten mittlerweile auch grundlegende Sortieralgorithmen, daher ist es von Vorteil, mehr zu üben. (Empfohlen: Java-Video-Tutorial)

Die im Artikel enthaltenen Codes sind alle in Java implementiert, umfassen jedoch nicht zu viele Java-Sprachfunktionen, und ich werde detaillierte Kommentare hinzufügen. hilft Ihnen, den Code zu verstehen und ihn in eine Programmiersprache umzuwandeln, mit der Sie vertraut sind.

Es gibt 10 gängige Sortieralgorithmen:

• Blasensortierung, Auswahlsortierung, Einfügungssortierung, die durchschnittliche Zeitkomplexität beträgt O(n² )
• Hill-Sortierung, Zusammenführungssortierung, Schnellsortierung, Heap-Sortierung, die durchschnittliche Zeitkomplexität beträgt O(nlogn)
• Zählsortierung, Radix-Sortierung, Bucket-Sortierung, die durchschnittliche Zeitkomplexität beträgt O(nlogn) Das ist es O(n + k)

Bevor Sie mit der Erläuterung des spezifischen Sortieralgorithmus beginnen, müssen Sie zunächst zwei Konzepte verstehen:

1. In-Place-Sortierung: bezieht sich auf das Sortieren Der Prozess belegt keinen zusätzlichen Speicherplatz und die Speicherplatzkomplexität beträgt O (1).
2. Stabilität des Sortieralgorithmus: Eine stabile Sortierung bedeutet, dass sich die Reihenfolge derselben Elemente nach dem Sortieren nicht ändert. Andernfalls wird dies als instabil bezeichnet. Zum Beispiel: Ein Array [3, 5, 1, 4, 9, 6, 6, 12] hat zwei 6er (zur Unterscheidung habe ich eine der 6er fett hervorgehoben), wenn es nach dem Sortieren so aussieht : [1, 3, 4, 5, 6, 6, 9, 12] (die fette 6 steht immer noch vorne), was zeigt, dass es sich um einen stabilen Sortieralgorithmus handelt.

2. Näher zu Hause

Die Idee der Blasensortierung ist eigentlich sehr einfach. Wenn die Größenbeziehung erfüllt ist, tauschen Sie die Positionen dieser beiden Daten aus. Durch Wiederholen dieses Vorgangs können die Daten sortiert werden.

Wenn es beispielsweise ein Array a[3,5,1,4,9,6] gibt, ist der erste Bubbling-Vorgang wie folgt:

Wiederholen Sie diesen Vorgang. Nach 6 Blasen ist die Datensortierung abgeschlossen.

Nach dieser Idee sollte es einfach sein, den folgenden Code zu schreiben, um die Blasensortierung zu implementieren:

public class BubbleSort {

    //data表示整型数组，n表示数组大小
    public static void bubbleSort(int[] data, int n){
        //数组大小小于等于1，无须排序
        if (n  data[j + 1]，交换两个数据的位置
                if (data[j] > data[j + 1]){
                    int temp = data[j];
                    data[j] = data[j + 1];
                    data[j + 1] = temp;
                }
            }
        }
    }
}

Aber dieser Sortieralgorithmus kann auch optimiert werden, wenn in der Blase kein Datenaustausch stattfindet Operation Wenn dies der Fall ist, bedeutet dies, dass die Sortierung abgeschlossen ist und keine Notwendigkeit besteht, den Blasenvorgang durchzuführen. Im obigen Beispiel lauten die Daten beispielsweise nach der ersten Blase [3,1,4,5,6,9] und nach einer weiteren Blase werden die Daten zu [1,3,4,5,6,9 ] ist die Sortierung zu diesem Zeitpunkt abgeschlossen und die Schleife kann beendet werden.

Um dieses Array zu sortieren, benötigt der obige Code also 6 Blasen, von denen 4 unnötig sind. So kann der Code optimiert werden:

public class BubbleSort {

    //优化后的冒泡排序
    //data表示整型数组，n表示数组大小
    public static void bubbleSort(int[] data, int n){
        //数组大小小于等于1，无须排序，返回空
        if (n  data[j + 1]，交换两个数据的位置
                if (data[j] > data[j + 1]){
                    int temp = data[j];
                    data[j] = data[j + 1];
                    data[j + 1] = temp;

                    flag = true;//表示有数据交换
                }
            }
            //如果没有数据交换，则直接退出循环
            if (!flag) break;
        }
    }
}

Okay, die Grundidee und der Code der Blasensortierung wurden implementiert. Zusammenfassend lässt sich sagen:

1. Die Blasensortierung basiert auf Datenvergleich
2. Die Zeitkomplexität im besten Fall ist O(n), die Zeitkomplexität im schlechtesten Fall ist O(n²) und die durchschnittliche Zeitkomplexität ist O(n² )
3. Bubble Sort ist ein In-Place-Sortieralgorithmus und stabil.

Das obige ist der detaillierte Inhalt vonDetaillierte Einführung in die Java-Blasensortierung (Codebeispiel). Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!