Ausführliche Erläuterung der Einfügungssortierung in der PHP-Sortieralgorithmusreihe

In diesem Artikel werden hauptsächlich die relevanten Informationen zur Einfügungssortierung in der PHP-Sortieralgorithmus-Reihe ausführlich vorgestellt. Interessierte Freunde können sich auf

Einfügungssortierung

Es ist eine bereits geordnete Datensequenz erforderlich, aber es ist erforderlich, dass die Datensequenz nach dem Einfügen noch geordnet ist Eine neue Sortiermethode – Einfügungssortierung. Die grundlegende Operation der Einfügungssortierung besteht darin, Daten in die bereits sortierten geordneten Daten einzufügen und so neue geordnete Daten mit der Zahl plus eins zu erhalten Die zeitliche Komplexität der Datensortierung beträgt O(n^2). Es handelt sich um eine stabile Sortiermethode. Der Einfügealgorithmus teilt das zu sortierende Array in zwei Teile: Der erste Teil enthält alle Elemente des Arrays mit Ausnahme des letzten Elements (wodurch das Array um einen weiteren Platz für eine Einfügeposition erweitert wird), und der zweite Teil enthält nur dieses Element (d. h. das einzufügende Element). Nachdem der erste Teil sortiert ist, wird dieses letzte Element in den sortierten ersten Teil eingefügt.

Prinzip

Die Grundidee der Direkteinfügungssortierung (Insertion Sort) ist: Jedes Mal, wenn ein zu sortierender Datensatz in den zuvor sortierten Datensatz eingefügt wird seine Schlüsselgröße Die entsprechende Position in der geordneten Teilsequenz, bis alle Datensätze eingefügt sind.

Angenommen, das Array ist ein[0…n-1].

1. Zunächst bildet a[0] einen geordneten Bereich und der ungeordnete Bereich ist a[1..n-1]. Sei i=1

2. Füge a[i] mit dem aktuellen geordneten Bereich a[0...i-1] zusammen, um ein geordnetes Intervall von a[0...i] zu bilden.
3.i++ und wiederholen Sie den zweiten Schritt, bis i==n-1. Sortierung abgeschlossen.

PHP-Code-Implementierung

function insertSort($arr){
  //获取需要排序的长度
  $length=count($arr);
  //假定第一个为有序的，所以从$i开始比较
  for ($i=1; $i <$length ; $i++) {
    //存放待比较的值
    $tmp=$arr[$i];
    for($j=$i-1;$j>=0;$j--){
      //若插入值比较小，则将后面的元素后移一位，并将值插入
      if($tmp<$arr[$j]){
        $arr[$j+1]=$arr[$j];
        $arr[$j]=$tmp;
      }else{
        break;
      }
    }
  }
  return $arr;
}

Algorithmus Zeitkomplexitätsberechnung

Im besten Fall (die Elemente sind bereits in der richtigen Reihenfolge angeordnet) : Dann müssen Sie nur n-1 Mal eine Schleife durchführen und die Zeitkomplexität ist O(n)

Im schlimmsten Fall (die Elemente sind in umgekehrter Reihenfolge): Die Anzahl der Schleifenanpassungen muss sein: [ n * ( n-1 ) ] / 2, die zeitliche Komplexität beträgt O (n ^ 2)
Die durchschnittliche zeitliche Komplexität beträgt: O (n ^ 2)

Das Obige ist der gesamte Inhalt dieses Artikels, I Ich hoffe, dass es für alle beim Lernen hilfreich sein wird, und ich hoffe, dass jeder die chinesische PHP-Website unterstützen wird.

Artikel, die Sie interessieren könnten:

Erklärung des Bucket-Sortieralgorithmus in PHP

Detaillierte Erläuterung der Probleme, die beim Entwickeln und Einrichten von Lazy Loading in Laravel Service Provider auftreten

PHP implementiert den Sortier-Heap-Sortieralgorithmus

Das obige ist der detaillierte Inhalt vonAusführliche Erläuterung der Einfügungssortierung in der PHP-Sortieralgorithmusreihe. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!