PHP-Sortieralgorithmus, Serieneinfügung, Sortierung, Beispielfreigabe

Dieser Artikel stellt allen die relevanten Informationen zur Einfügungssortierung in der PHP-Sortieralgorithmus-Reihe im Detail vor. Ich hoffe, dass er jedem helfen kann.

Einfügungssortierung

Es gibt eine bereits geordnete Datensequenz, und es ist erforderlich, eine Zahl in diese bereits sortierte Datensequenz einzufügen, aber es ist erforderlich, dass diese Daten Die Reihenfolge wird immer noch eingefügt. Zu diesem Zeitpunkt wird eine neue Sortiermethode verwendet - die Einfügungssortierung. Der grundlegende Vorgang der Einfügungssortierung besteht darin, Daten in die sortierten geordneten Daten einzufügen, um einen neuen, individuellen Algorithmus zu erhalten zum Sortieren einer kleinen Datenmenge, und die zeitliche Komplexität 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 Ordnung): Dann müssen Sie nur noch n-1 Schleifen durchlaufen, und die Zeitkomplexität beträgt O(n)
Im schlimmsten Fall (die Elemente sind in umgekehrter Reihenfolge): Die Anzahl der Schleifenanpassungen muss sein: [ n * (n -1) ] / 2, die Zeitkomplexität beträgt O(n^2)
Die durchschnittliche Zeitkomplexität beträgt: O(n^2)

Verwandte Empfehlungen:

PHP-Implementierung Bucket Sortieralgorithmus-Beispielfreigabe

Detaillierte Erläuterung der Heap-Sortierung des PHP-Sortieralgorithmus

PHP-Lernfreigabe für einfache Auswahlsortieralgorithmen

Das obige ist der detaillierte Inhalt vonPHP-Sortieralgorithmus, Serieneinfügung, Sortierung, Beispielfreigabe. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!