Ausführliche Erklärung der Verwendung der PHP-Blasensortierung

Dieses Mal erkläre ich Ihnen ausführlich die Verwendung von PHP Bubble Sort und welche Vorsichtsmaßnahmen bei der Verwendung von PHP Bubble Sort gelten. Das Folgende ist ein praktischer Fall Schauen Sie mal rein.

Grundidee:

Blasensortierung ist eine Art Austauschsortierung: Der Schlüssel zum paarweisen Vergleich benachbarter Datensätze. Wenn sie umgekehrt sind, werden sie ausgetauscht, bis keine Datensätze in umgekehrter Reihenfolge mehr vorhanden sind.

Die einfachste Sortierimplementierung:

Werfen wir zunächst einen Blick auf die häufig verwendeten Sortiermethoden, bevor wir verschiedene Sortiermethoden erlernen (zumindest). Für mich ist das so nur eine einfache Austauschart. Die Idee besteht einfach darin: Beginnen Sie mit dem ersten Schlüsselwort, vergleichen Sie jedes Schlüsselwort mit allen folgenden Schlüsselwörtern und tauschen Sie sie aus, um den Mindestwert zu erhalten. Dieser Algorithmus ist jedoch sehr ineffizient.

Blasensortierungsalgorithmus: Er durchläuft wiederholt das zu sortierende Array und vergleicht jeweils zwei Elemente, wenn sie sich in der befinden falsche Bestellung Einfach umtauschen. 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 größere Elemente im Array nach dem Sortieren allmählich an den hinteren Rand des Arrays „sinken“, während kleinere Elemente allmählich an den vorderen Rand des Arrays „schweben“. daher der Name.

Der Blasensortierungsalgorithmus funktioniert wie folgt: (von hinten nach vorne)

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

2. Machen Sie die gleiche Arbeit für jedes Paar benachbarter Elemente, vom ersten Paar am Anfang bis zum letzten Paar am Ende. Zu diesem Zeitpunkt sollte das letzte Element die größte Zahl sein.

3. Wiederholen Sie die obigen Schritte für alle Elemente außer dem letzten.
4. Wiederholen Sie die obigen Schritte jedes Mal für immer weniger Elemente, bis keine Zahlenpaare mehr zum Vergleichen vorhanden sind.

Sie verstehen es vielleicht nicht, wenn Sie die Textbeschreibung lesen, aber schauen Sie sich den Code an:

//这里使用了类型提示（type hint） array，不熟悉或者不习惯的同学大可去掉，不影响运算结果
function MySort(array &$arr){
  $length = count($arr);
  for($i = 0;$i < $length - 1;$i ++){
    for($j = $i + 1;$j < $length;$j ++){
      //将小的关键字放前面
      if($arr[$i] > $arr[$j]){
        $temp = $arr[$i];
        $arr[$i] = $arr[$j];
        $arr[$j] = $temp;
      }
    }
  }
}
$arr = array(9,1,5,8,3,7,4,6,2);
MySort($arr);
print_r($arr);

Verbesserung des Blasensortierungsalgorithmus:

Kann der obige Blasensortierungsalgorithmus noch optimiert werden? Die Antwort ist ja. Stellen Sie sich vor, wenn die Reihenfolge, die wir sortieren möchten, {2,1,3,4,5,6,7,8,9} ist, d. h. bis auf das erste und zweite Schlüsselwort muss alles andere ausgetauscht werden . Es ist bereits die normale Reihenfolge. Wenn i = 0, 2 und 1 sind, ist die Sequenz zu diesem Zeitpunkt bereits in Ordnung, aber der Algorithmus führt immer noch i = 2 bis 9 aus, obwohl in jeder Schleife keine Daten ausgetauscht wurden befolgt wurden, waren weitgehend überflüssig.

Wenn i = 2, haben wir 9 und 8, 8 und 7, ·······, 3 und 2 ohne Datenaustausch verglichen, was bedeutet, dass diese Sequenz bereits in Ordnung ist. Es ist notwendig, fortzufahren die anschließende Beurteilungsarbeit (in der nachfolgenden Arbeit findet kein Datenaustausch statt und es ist sinnlos, dies noch einmal durchzuführen). Um diese Idee zu verwirklichen, müssen wir den Code verbessern und ein Mark-Variablen-Flag hinzufügen, um die Verbesserung dieses Algorithmus zu realisieren:

//交换方法
function swap(array &$arr,$a,$b){
  $temp = $arr[$a];
  $arr[$a] = $arr[$b];
  $arr[$b] = $temp;
}
//冒泡排序
function BubbleSort(array &$arr){
  $length = count($arr);
  for($i = 0;$i < $length - 1;$i ++){
    //从后往前逐层上浮小的元素
    for($j = $length - 2;$j >= $i;$j --){
      //两两比较相邻记录
      if($arr[$j] > $arr[$j + 1]){
        swap($arr,$j,$j+1);
      }
    }
  }
}

Der Schlüssel zur Codeänderung ist die

for-Schleife wird die Beurteilung, ob das Flag wahr ist, hinzugefügt. Nach einer solchen Verbesserung wurde die Leistung der Blasensortierung verbessert und die bedeutungslose Schleifenbeurteilung kann vermieden werden, wenn die Reihenfolge bereits in Ordnung ist.

Die Gesamtzeitkomplexität des Blasenalgorithmus beträgt O(n^2)

.

Bubble Sort ist eine stabile Sortierung.

Ich glaube, dass Sie die Methode beherrschen, nachdem Sie den Fall in diesem Artikel gelesen haben. Weitere spannende Informationen finden Sie in anderen verwandten Artikeln auf der chinesischen PHP-Website!

Empfohlene Lektüre:

PHP Hill-Sortierfallanalyse

Beispielanalyse für den PHP-Heap-Sortieralgorithmus

Das obige ist der detaillierte Inhalt vonAusführliche Erklärung der Verwendung der PHP-Blasensortierung. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!