PHP-Codebeispiel zur Implementierung der Einfügungssortierung

Der Inhalt dieses Artikels befasst sich mit dem Codebeispiel für die Einfügungssortierung in PHP. Ich hoffe, dass er für Sie hilfreich ist.

Das war's mit dem Sortieralgorithmus. In diesem Artikel handelt es sich um Blasensortierung, Schnellsortierung, Auswahlsortierung und Einfügungssortierung. Diese vier Algorithmen sind relativ einfach und leicht zu verstehen. Komplexere Algorithmen werden ihre Hässlichkeit nicht zur Schau stellen, um andere nicht in die Irre zu führen.

Insertion Sort

Insertion Sort (englisch: Insertion Sort) ist ein einfacher und intuitiver Sortieralgorithmus. Es funktioniert, indem es eine geordnete Sequenz erstellt. Bei unsortierten Daten wird die sortierte Sequenz von hinten nach vorne durchsucht, um die entsprechende Position zu finden und einzufügen. Bei der Implementierung der Einfügungssortierung wird normalerweise die In-Place-Sortierung verwendet (d. h. eine Sortierung, die nur O(1) zusätzlichen Platz beansprucht). Daher ist es während des Scanvorgangs erforderlich, die Sortierung wiederholt und schrittweise zu verschieben Sortiert Elemente rückwärts und bietet Platz für das Einfügen des neuesten Elements.

Im Allgemeinen wird die Einfügungssortierung auf Arrays mithilfe von In-Place implementiert. Der spezifische Algorithmus wird wie folgt beschrieben:

1. Beginnend mit dem ersten Element kann davon ausgegangen werden, dass das Element sortiert wurde

2. Nehmen Sie das nächste Element heraus und fahren Sie von hinten fort Sortierte Elementsequenz Vorab scannen

3. Wenn das Element (sortiert) größer als das neue Element ist, verschieben Sie das Element an die nächste Position

4. Wiederholen Sie Schritt 3, bis das sortierte Element vorhanden ist Es wurde festgestellt, dass es kleiner oder gleich ist Die Position des neuen Elements

5. Nach dem Einfügen des neuen Elements in die Position

6 aus Wikipedia. Der Fokus liegt auf den Schritten 2–5.

Animationsdemonstration

Beispiel

<?php $arr = [33, 24, 8, 21, 2, 23, 3, 32, 16];

function insertSort($arr)
{
    $count = count($arr);

    if ($count < 2) {
        return $arr;
    }

    for ($i = 1; $i < $count; $i++) {
        // 当前值
        $temp = $arr[$i];
        for ($k = $i - 1; $k >= 0; $k--) {
            // 条件成立，比较值后挪一位，将当前值替换成比较值
            // 倒序 $temp > $arr[$k]
            if ($temp  2 [1] => 3 [2] => 8 [3] => 16 [4] => 21 [5] => 23 [6] => 24 [7] => 32 [8] => 33 )

Das obige ist der detaillierte Inhalt vonPHP-Codebeispiel zur Implementierung der Einfügungssortierung. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!