PHP-Sortierung: Algorithmusidee und Algorithmusimplementierung der PHP-Einfügungssortierung

Der Inhalt dieses Artikels befasst sich mit der PHP-Sortierung: Die Algorithmusidee und die Algorithmusimplementierung der PHP-Einfügungssortierung. Ich hoffe, dass es für Sie hilfreich ist.

Einführung in den Algorithmus:

Hier verwenden wir noch ein Beispiel aus „Dahua Data Structure“:

Poker ist etwas, das fast jeder von uns gespielt hat. Wenn wir beginnen, teilt 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 4 in eine geordnete Liste mit ein zwei Elemente 3
3 4 5 in der geordneten Liste von 5 In der geordneten Liste von 6
2 3 4 5 6

Die Grundidee der Direkteinfügungssortierung ist: Nehmen Sie das erste heraus Wählen Sie jedes Mal ein Element aus der ungeordneten Liste aus und fügen Sie es an der entsprechenden Position in 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. 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.

Implementierung des Einfügesortieralgorithmus:

// 直接插入排序
function swap(&$arr,$a,$b)
{
$temp    = $arr[$a];
$arr[$a] = $arr[$b];
$arr[$b] = $temp;
}
function insertSort(&$arr)
{
$count = count($arr);
for ($i=1; $i = 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)
}

Verwandte Empfehlungen:

PHP-Array-Sortiermethodenfreigabe (Blasensortierung, Auswahlsortierung)

PHP implementiert Heap-Sortierung, PHP-Heap-Sortierung_PHP-Tutorial

Das obige ist der detaillierte Inhalt vonPHP-Sortierung: Algorithmusidee und Algorithmusimplementierung der PHP-Einfügungssortierung. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!