Implementierungsschritte des Einfügungssortierungsalgorithmus in PHP

Einfügungssortierungsalgorithmus in PHP

Einfügungssortierung ist ein einfacher und intuitiver Sortieralgorithmus. Er erstellt eine geordnete Sequenz und fügt unsortierte Daten nacheinander in die sortierte Sequenz ein, um eine geordnete Sequenz zu erhalten. In PHP können wir den Einfügungssortierungsalgorithmus durch die folgenden Schritte implementieren.

Schritt 1: Definieren Sie eine Funktion insertSort, die ein zu sortierendes Array als Parameter empfängt.

function insertionSort($arr) {
  $n = count($arr);
  for ($i = 1; $i < $n; $i++) {
    $key = $arr[$i];
    $j = $i - 1;

    while ($j >= 0 && $arr[$j] > $key) {
      $arr[$j + 1] = $arr[$j];
      $j = $j - 1;
    }
    $arr[$j + 1] = $key;
  }

  return $arr;
}

Schritt 2: Rufen Sie die Funktion insertSort im Hauptprogramm auf und übergeben Sie das zu sortierende Array.

$unsortedArray = [5, 2, 1, 7, 3];
$sortedArray = insertionSort($unsortedArray);

Schritt 3: Definieren Sie eine for-Schleife, um das sortierte Array auszugeben.

$n = count($sortedArray);
for ($i = 0; $i < $n; $i++) {
  echo $sortedArray[$i] . " ";
}

Der vollständige Code lautet wie folgt:

Der obige Code implementiert den Einfügungssortierungsalgorithmus. Die Kernidee des Algorithmus besteht darin, das zu sortierende Array in zwei Teile, sortiert und unsortiert, zu unterteilen und ein geordnetes Ergebnis zu erhalten, indem unsortierte Elemente nacheinander in den sortierten Teil eingefügt werden. Im Code verwenden wir eine for-Schleife, um das zu sortierende Array zu durchlaufen und das aktuelle Element an der entsprechenden Position einzufügen. Die innere While-Schleife wird verwendet, um die Elemente des sortierten Abschnitts kontinuierlich zu vergleichen und zu verschieben, bis die entsprechende Position gefunden ist.

Die zeitliche Komplexität des Einfügungssortierungsalgorithmus beträgt O(n^2), wobei n die Länge des zu sortierenden Arrays darstellt. Da der Algorithmus nur Vergleichs- und Bewegungsoperationen benachbarter Elemente umfasst, beträgt die Raumkomplexität O(1) und es handelt sich um einen In-Place-Sortieralgorithmus.

Zusammenfassung: Durch die oben genannten Schritte haben wir den Einfügungssortierungsalgorithmus erfolgreich in PHP implementiert. Der Algorithmus ist einfach und effektiv und eignet sich zum Sortieren kleiner Daten. Wenn in praktischen Anwendungen das zu sortierende Array größer ist oder eine höhere Leistung erforderlich ist, können andere schnellere Sortieralgorithmen in Betracht gezogen werden.

Das obige ist der detaillierte Inhalt vonImplementierungsschritte des Einfügungssortierungsalgorithmus in PHP. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!