JavaScript implementiert die Einfügungsart des klassischen Sortieralgorithmus

Obwohl die Code-Implementierung der Einfügungssortierung nicht so einfach und grob ist wie die Blasensortierung und Auswahlsortierung, sollte ihr Prinzip am einfachsten zu verstehen sein, da jeder, der Poker gespielt hat, es in Sekundenschnelle verstehen kann. Wie beim Sortieren einer Pokerhand beginnen wir mit einer leeren linken Hand und den Karten auf dem Tisch mit der Vorderseite nach unten. Anschließend nehmen wir jeweils eine Karte vom Tisch und stecken diese an der richtigen Stelle in die linke Hand. Um die richtige Position einer Karte zu finden, vergleichen wir sie mit jeder Karte, die sich bereits in der Hand befindet, von rechts nach links. Die Karten in der linken Hand sind immer sortiert und waren ursprünglich die obersten Karten im Stapel auf dem Tisch.

1) Algorithmusprinzip

Die Algorithmusbeschreibung der Einfügungssortierung (Insertion-Sort) ist ein einfacher und intuitiver Sortieralgorithmus. Es funktioniert, indem es eine geordnete Sequenz erstellt. Bei unsortierten Daten scannt es die sortierte Sequenz von hinten nach vorne, findet die entsprechende Position und fügt sie ein. 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 müssen die sortierten Elemente während des Scanvorgangs von hinten nach vorne wiederholt und schrittweise sortiert werden nach hinten verschoben und bietet so Platz zum Einfügen des neuesten Elements.

2) Beschreibung und Implementierung des Algorithmus

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

f35d6e602fd7d0f0edfa6f7d103c1b57 Das Element kann als sortiert betrachtet werden.

2cc198a1d5eb0d3eb508d858c9f5cbdb nach dem sortierten Element Von hinten nach vorne in der Reihenfolge scannen

5bdf4c78156c7953567bb5a0aef2fc53 Wenn das Element (sortiert) größer als das neue Element ist, verschieben Sie das Element an die nächste Position; 23889872c2e8594e0f446a471a78ec4c Wiederholen Sie die Schritte 3. Bis Sie eine Position finden, an der das sortierte Element kleiner oder gleich dem neuen Element ist

43ad812d3a971134e40facaca816c822

efbfa0de8737dc86eae413541a49df20 Wiederholen Sie die Schritte 2–5.

3) JavaScript-Code-Implementierung

Verbesserte Einfügesortierung: Verwenden Sie die binäre Suche, wenn Sie die Einfügeposition finden.

function insertSort(arr) { 
    for (var i = 1; i < arr.length; i++) { 
      var temp = arr[i]; 
      var j = i - 1; 
      while (j >= 0 && arr[j] > temp) { 
        arr[j + 1] = arr[j]; 
         j--; 
      } 
      arr[j + 1] = temp; 
    } 
    return arr; 
 } 
var arr = [1, 45, 37, 5, 48, 15, 37, 26, 29, 2, 46, 4, 17, 50, 52]; 
console.log(insertSort(arr));

Schritte:
                                                                Die binäre Suche findet die Position der ersten Zahl in der Folge, die größer ist                                    mit dem neuen Element, das an dieser Position eingefügt wird;                              >

Am besten Fall: Das Eingabearray wird in aufsteigender Reihenfolge sortiert. T(n) = O(n)

Schlimmster Fall: Das Eingabearray wird in absteigender Reihenfolge sortiert. T(n) = O(n2)
Durchschnittliche Situation: T(n) = O(n2)

Das Obige ist der gesamte Inhalt dieses Artikels, ich hoffe, dass er für das Studium aller hilfreich sein wird. Ich hoffe auch, dass jeder mehr über die chinesische PHP-Website erfahren wird.

function binaryInsertionSort(arr) { 
   for (var i = 1; i < arr.length; i++) { 
     var key = arr[i],left = 0,right = i - 1; 
     while (left <= right) { 
        var middle = parseInt((left + right) / 2); 
        if (key < arr[middle]) { 
          right = middle - 1; 
        } else { 
          left = middle + 1; 
        } 
     } 
     for (var j = i - 1; j >= left; j--) { 
        arr[j + 1] = arr[j]; 
     } 
     arr[left] = key; 
    } 
    return arr; 
} 
var arr = [1, 45, 37, 5, 48, 15, 37, 26, 29, 2, 46, 4, 17, 50, 52]; 
console.log(binaryInsertionSort(arr));

Weitere Artikel zum Thema Einfügungssortierung mit JavaScript zur Implementierung des klassischen Sortieralgorithmus finden Sie auf der chinesischen PHP-Website!