Codebeispiel für die Implementierung der Blasensortierung in PHP

Dieser Artikel bietet Ihnen ein Codebeispiel für die Implementierung der Blasensortierung in PHP. Ich hoffe, dass er Ihnen als Referenz dienen wird.

Bubble Sort ist ein relativ einfacher und häufig verwendeter Algorithmus und auch die am häufigsten gestellte Frage in Interviews. Ich habe das Gefühl, dass ich nicht in der Lage bin, ein tieferes Verständnis zu erlangen, daher werde ich den Inhalt einiger Materialien unten aufzeichnen. Am Ende des Artikels befindet sich ein Link zum Originaltext.

Blasensortierung

Blasensortierung (englisch: Bubble Sort) ist ein einfacher Sortieralgorithmus. Es durchläuft wiederholt die zu sortierende Sequenz, vergleicht jeweils zwei Elemente und vertauscht sie, wenn sie in der falschen Reihenfolge sind. Der Besuch des Arrays wird wiederholt, bis kein Austausch mehr erforderlich ist, was bedeutet, dass das Array sortiert wurde. Der Name dieses Algorithmus rührt von der Tatsache her, dass kleinere Elemente durch den Austausch langsam an die Spitze des Arrays „schweben“.

Blasensortierung erfordert O(n2) Vergleiche für n Elemente und kann an Ort und Stelle sortiert werden. Obwohl dieser Algorithmus einer der am einfachsten zu verstehenden und zu implementierenden Sortieralgorithmen ist, ist er für die Sortierung von Arrays mit einer großen Anzahl von Elementen sehr ineffizient.

Der Blasensortierungsalgorithmus funktioniert wie folgt:

Vergleicht benachbarte 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. Nachdem dieser Schritt abgeschlossen ist, ist das letzte Element die größte Zahl.

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.

Das Obige ist die Einführung in Wikipedia. Wie Sie sehen, ist das Prinzip nicht kompliziert. Bei großen Datenmengen ist dies jedoch keine gute Wahl.

Animationsdemonstration

Es ist zu beachten, dass die Reihenfolge des Codes im Bild unten und im Beispiel umgekehrt ist.

Instanz

<?php $arr = [33, 24, 8, 21, 2, 23, 3, 32, 16];

function bubbleSort($arr)
{
    if (!is_array($arr)) {
        return false;
    }

    $count = count($arr);

    if ($count < 2) {
        return $arr;
    }

    for ($i = 0; $i < $count; $i++) {
        for ($k = $i + 1; $k < $count; $k++) {
            // $arr[$i] 和 $arr[$k] 是相邻的两个值
            if ($arr[$i] > $arr[$k]) {
                // 前者大于后者，调换位置
                // 如果想要按照从大到小进行排序，改为 $arr[$i]  2 [1] => 3 [2] => 8 [3] => 16 [4] => 21 [5] => 23 [6] => 24 [7] => 32 [8] => 33 )

Das obige ist der detaillierte Inhalt vonCodebeispiel für die Implementierung der Blasensortierung in PHP. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!