PHP-Sortieralgorithmus Straight Insertion Sort

In diesem Artikel wird hauptsächlich der PHP-Sortieralgorithmus Straight Insertion Sort (Straight Insertion Sort) vorgestellt. Er analysiert detailliert die Prinzipien und Implementierungstechniken des Straight Insertion Sort-Algorithmus in Form von Beispielen.

Das Beispiel in diesem Artikel beschreibt den PHP-Sortieralgorithmus Straight Insertion Sort. Teilen Sie es als Referenz mit allen. Die Details lauten wie folgt:

Einführung in den Algorithmus:

Hier verwenden wir immer noch einen von „Dahua Data“. Struktur“ Beispiel:

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 Reihe nach in die geordnete Liste eingefügt 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. Bei der Direkteinfügungssortierung wird der zu vergleichende Wert mit seinem vorherigen Wert verglichen, 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);

Laufergebnis:

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.

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

Verwandte Empfehlungen:

PHP-Sortieralgorithmus Shell Sort (Shell Sort)

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