PHP-Sortieralgorithmus Bubble Sort (Bubble Sort)

Dieser Artikel stellt hauptsächlich die Implementierungsmethode des PHP-Sortieralgorithmus vor. Er bezieht sich auf den Algorithmus in der Dahua-Datenstruktur und analysiert das Prinzip und die damit verbundenen Implementierungstechniken im Detail in Form von Beispielen siehe

Dieser Artikel beschreibt die Implementierungsmethode des PHP-Sortieralgorithmus Bubble Sort (Bubble Sort) anhand von Beispielen. Teilen Sie es als Referenz mit allen. Die Details lauten wie folgt:

Grundidee:

Bubble Sort ist eine Art Austauschsortierung. Seine Grundidee ist: Vergleichen Sie die Schlüsselwörter benachbarter Datensätze paarweise und tauschen Sie sie aus, wenn sie in umgekehrter Reihenfolge vorliegen, bis keine Datensätze mehr in umgekehrter Reihenfolge 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 alles Erfüllen Sie die Idee der Blasensortierung des „paarweisen Vergleichs benachbarter Datensätze“, es handelt sich lediglich um eine einfache Austauschsortierung. 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:

//这里使用了类型提示（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);

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:

Verbesserung des Blasensortierungsalgorithmus:

//交换方法
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);
      }
    }
  }
}

„Dahua Data Structure“ ist in der Tat ein gutes Buch. Es führt uns auch in die Verbesserung des Blasensortierungsalgorithmus ein Kopieren Sie es einfach hierher. Aussage:

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 eine Flag-Variable hinzufügen, um die Verbesserung dieses Algorithmus zu realisieren:

Der Schlüssel zur Codeänderung besteht darin, eine Beurteilung darüber hinzuzufügen, ob das Flag in der for-Schleife der i-Variablen wahr ist. Nach solchen Verbesserungen wurde die Leistung der Blasensortierung verbessert, wodurch das vermieden werden kann Problem, in Situationen bereits in Ordnung zu sein.

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

.

//交换方法
function swap(array &$arr,$a,$b){
  $temp = $arr[$a];
  $arr[$a] = $arr[$b];
  $arr[$b] = $temp;
}
/冒泡排序的优化(如果某一次循环的时候没有发生元素的交换，则整个数组已经是有序的了)
function BubbleSort1(array &$arr){
  $length = count($arr);
  $flag = TRUE;
  for($i = 0;($i < $length - 1) && $flag;$i ++){
    $flag = FALSE;
    for($j = $length - 2;$j >= $i;$j --){
      if($arr[$j] > $arr[$j + 1]){
        swap($arr,$j,$j+1);
        $flag = TRUE;
      }
    }
  }
}

Bubble Sort ist eine stabile Sortierung.

Auf diesen Artikel wird von „Dahua Data Structure“ verwiesen. Er wird hier nur zum späteren Nachschlagen aufgezeichnet.

Verwandte Empfehlungen:

PHP-Sortieralgorithmus Simple Selection Sort (Simple Selection Sort)

PHP-Sortieralgorithmus Direct Insertion Sort (Straight Insertion). Sortieren)

PHP-Sortieralgorithmus Shell Sort (Shell Sort)

Das obige ist der detaillierte Inhalt vonPHP-Sortieralgorithmus Bubble Sort (Bubble Sort). Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!