Sortierfallanalyse für PHP-Direkteinfügungen

Dieses Mal werde ich Ihnen eine Fallanalyse der PHP-Direkteinfügungssortierung vorstellen. Was sind die Vorsichtsmaßnahmen für die PHP-Direkteinfügungssortierung?

Einführung in den Algorithmus:

Poker ist ein Spiel, das fast jeder von uns gespielt hat. Wenn wir beginnen, gibt normalerweise eine Person die Karten aus, und alle anderen ziehen und sortieren die Karten. Wenn die erste Karte, die Sie ziehen, eine 3 ist, legen wir natürlich die 3 ein. Gehen Sie zur Vorderseite der 5 Karte ist 4, finde sie zwischen 3 und 5; die vierte Karte ist 6, lege sie hinter 5; die fünfte Karte ist 2, füge sie vor 3 ein;…. Wenn wir schließlich alle Karten gezogen haben, werden die Karten in unseren Händen von klein nach groß (Punkte) sortiert.

Sehen wir uns diese Sequenz an:

5 3 3 // Füge 3 in eine geordnete Liste mit nur einem Element ein 5
3 5 4 4 Füge 6 ein in die geordnete Liste mit zwei Elementen 3 5
3 4 5 6 6 // Füge 6 in die geordnete Liste mit zwei Elementen 3 4 5
3 4 5 6 2 2 in eine geordnete Liste mit zwei Elementen 3 4 5 6 ein
2 3 4 5 6

Grundidee:

Die Grundidee der Direkteinfügungssortierung ist: Nehmen Entfernen Sie jedes Mal das erste Element aus der ungeordneten Liste und fügen Sie es an der entsprechenden Position der geordneten Liste ein, sodass die geordnete Liste geordnet bleibt.

Der erste Durchgang vergleicht die ersten beiden Zahlen und fügt dann die zweite Zahl entsprechend der Größe in die geordnete Liste ein; der zweite Durchgang scannt die dritten Daten und die ersten beiden Zahlen von hinten nach vorne und die dritte Zahl wird der Größe nach in die geordnete Liste eingefügt; dies wird der Reihe nach fortgesetzt und der gesamte Sortiervorgang ist nach (n-1) Scans abgeschlossen.

Direkte Einfügungssortierung besteht aus zwei Ebenen verschachtelter Schleifen. Die äußere Schleife identifiziert und bestimmt die zu vergleichenden Werte. Die innere Schleife bestimmt die endgültige Position der zu vergleichenden Werte. Die direkte Einfügungssortierung vergleicht den zu vergleichenden Wert mit seinem vorherigen Wert, sodass die äußere Schleife beim zweiten Wert beginnt. Wenn der aktuelle Wert größer als der zu vergleichende Wert ist, wird der Schleifenvergleich fortgesetzt, bis ein kleinerer Wert als der zu vergleichende Wert gefunden wird und der zu vergleichende Wert an der nächsten Position platziert wird, wodurch der Zyklus beendet wird.

Die grundlegende Methode der Einfügungssortierung ist: Bei jedem Schritt wird ein zu sortierender Datensatz entsprechend der Größe seines Schlüssels an der entsprechenden Position in der zuvor sortierten Reihenfolge eingefügt, bis alle Datensätze eingefügt sind.

Algorithmusimplementierung:

<?php
//直接插入排序
function swap(array &$arr,$a,$b){
  $temp = $arr[$a];
  $arr[$a] = $arr[$b];
  $arr[$b] = $temp;
}
function InsertSort(array &$arr){
  $count = count($arr);
  //数组中第一个元素作为一个已经存在的有序表
  for($i = 1;$i < $count;$i ++){
    $temp = $arr[$i];   //设置哨兵
    for($j = $i - 1;$j >= 0 && $arr[$j] > $temp;$j --){
      $arr[$j + 1] = $arr[$j];    //记录后移
    }
    $arr[$j + 1] = $temp;   //插入到正确的位置
  }
}
$arr = array(9,1,5,8,3,7,4,6,2);
InsertSort($arr);
var_dump($arr);

Laufendes Ergebnis:

array(9) {
 [0]=>
 int(1)
 [1]=>
 int(2)
 [2]=>
 int(3)
 [3]=>
 int(4)
 [4]=>
 int(5)
 [5]=>
 int(6)
 [6]=>
 int(7)
 [7]=>
 int(8)
 [8]=>
 int(9)
}

Die zeitliche Komplexität des Sortieralgorithmus für direkte Einfügung beträgt O(n^2).

Direkteinfügungssortierung 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:

Detaillierte Erläuterung der Schritte zur Verwendung des PHP-Schnellsortierungsalgorithmus

Detaillierte Erläuterung der Schritte Werbeplakate mit PHP generieren

Das obige ist der detaillierte Inhalt vonSortierfallanalyse für PHP-Direkteinfügungen. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!