Implementieren Sie die Einfügungssortierung mithilfe von JavaScript, um ein Array von Zahlen in aufsteigender Reihenfolge zu sortieren

Die Kunst der Array-Sortierung ist in der Welt der Programmierung von entscheidender Bedeutung, da sie eine effiziente Organisation und Bearbeitung von Daten ermöglicht. Wenn es darum geht, einen zuverlässigen Sortieralgorithmus zu implementieren, ist die Einfügungssortierung eine vielseitige und effiziente Wahl. In diesem Artikel tauchen wir in die komplexe Welt von JavaScript ein und untersuchen den Prozess der Implementierung einer Einfügungssortierung, um ein Array von Zahlen in aufsteigender Reihenfolge zu sortieren. Durch das Verständnis der zugrunde liegenden Mechanismen des Algorithmus und die Nutzung der Leistungsfähigkeit von JavaScript können Entwickler das Potenzial zum effizienten Sortieren und Organisieren numerischer Daten freisetzen und so die Anwendungsleistung und Benutzerfreundlichkeit verbessern.

Problemstellung

Die aktuelle Herausforderung besteht darin, einen Einfügungssortierungsalgorithmus mithilfe von JavaScript zu implementieren, um ein Array von Zahlen in aufsteigender Reihenfolge zu sortieren. Das Hauptziel besteht darin, ein Programm zu entwerfen, das die Elemente eines bestimmten Arrays intelligent neu anordnen kann und dabei sicherstellt, dass jedes nachfolgende Element basierend auf seinem numerischen Wert an der richtigen Position relativ zum vorherigen Element platziert wird. Nehmen wir zum Beispiel an, wir stellen ein Array

bereit

[9, 2, 7, 4, 1]

Nach der Ausführung des Einfügungssortierungsalgorithmus ist das erwartete Ergebnis ein Array in aufsteigender Reihenfolge, z. B.

[1, 2, 4, 7, 9]

Methode

In diesem Artikel werden wir verschiedene Möglichkeiten zur Lösung der oben genannten Probleme in JavaScript sehen -

• Grundlegende Einfügungssortierung

• Binäre Einfügungssortierung

• Rekursive Einfügungssortierung

Methode 1: Grundlegende Einfügungssortierung

Der grundlegende Einfügungssortierungsalgorithmus verwaltet ein sortiertes Unterarray innerhalb des Arrays. Beginnend mit dem zweiten Element wird jedes Element mit dem vorherigen Element im Subarray verglichen und nach rechts verschoben, wenn es kleiner ist. Dieser Vorgang wird fortgesetzt, bis die richtige Position gefunden ist und das Element eingefügt wird. Dieser Vorgang wird für alle Elemente wiederholt, sodass ein vollständig sortiertes Array entsteht.

Beispiel

Die Funktion „insertionSort“ verwendet ein Array arr als Eingabe und gibt ein Array zurück, das mit dem Einfügungssortierungsalgorithmus sortiert wurde. Es iteriert ausgehend vom zweiten Element und speichert es in der aktuellen Variablen. Die while-Schleife vergleicht das aktuelle Element mit dem vorherigen Element im sortierten Subarray und verschiebt das größere Element nach rechts. Die Schleife wird fortgesetzt, bis der Anfang des Arrays erreicht ist oder ein kleineres Element gefunden wird. Das aktuelle Element wird dann an der richtigen Position in das sortierte Subarray eingefügt. Dieser Vorgang wird für alle Elemente wiederholt, sodass ein sortiertes Array entsteht.

function insertionSort(arr) {
   for (let i = 1; i < arr.length; i++) {
      let current = arr[i];
      let j = i - 1;
      while (j >= 0 && arr[j] > current) {
         arr[j + 1] = arr[j];
         j--;
      }
      arr[j + 1] = current;
   }
   return arr;
}
 
const arr = [9, 2, 7, 4, 1];
console.log(insertionSort(arr));

Ausgabe

Das Folgende ist die Konsolenausgabe -

[ 1, 2, 4, 7, 9 ]

Methode 2: Binäre Einfügungssortierung

Der binäre Einfügungssortierungsalgorithmus verbessert die Effizienz der einfachen Einfügungssortierung, indem er eine binäre Suche im sortierten Subarray verwendet, um die korrekte Position jedes Elements zu bestimmen. Anstelle einer linearen Suche wird eine binäre Suche durchgeführt, indem das aktuelle Element mit dem mittleren Element des Subarrays verglichen und die Suchgrenzen entsprechend angepasst werden. Sobald der Einfügepunkt festgelegt ist, wird das Element nach rechts verschoben, um Platz zu schaffen, und das aktuelle Element wird eingefügt. Dieser Vorgang wird für alle Elemente wiederholt, sodass ein vollständig sortiertes Array entsteht.

Beispiel

Die Funktion

binaryInsertionSort nimmt ein Array arr und gibt ein Array zurück, das mit dem binären Einfügungssortierungsalgorithmus sortiert wurde. Es wird ausgehend vom zweiten Element iteriert, vorausgesetzt, das erste Element ist sortiert. Das aktuelle Element wird in der aktuellen Variablen gespeichert. Der Algorithmus führt eine binäre Suche in einem sortierten Subarray durch, um die korrekte Position des aktuellen Elements zu finden, indem er es mit dem mittleren Element vergleicht und die Suchgrenzen anpasst. Sobald die Position gefunden ist, verschiebt der Algorithmus das Element nach rechts und fügt das aktuelle Element an der richtigen Position ein. Dieser Vorgang wird für alle Elemente wiederholt, sodass ein sortiertes Array entsteht.

function binaryInsertionSort(arr) {
   for (let i = 1; i < arr.length; i++) {
      let current = arr[i];
      let left = 0;
      let right = i - 1;
      while (left <= right) {
         let mid = Math.floor((left + right) / 2);
         if (current < arr[mid]) {
            right = mid - 1;
         } else {
            left = mid + 1;
         }
      }
      for (let j = i - 1; j >= left; j--) {
         arr[j + 1] = arr[j];
      }
      arr[left] = current;
   }
   return arr;
}
 
const arr = [9, 2, 7, 4, 1];
console.log(binaryInsertionSort(arr));

Ausgabe

Das Folgende ist die Konsolenausgabe -

[ 1, 2, 4, 7, 9 ]

Methode 3: Rekursive Einfügungssortierung

Der rekursive Einfügungssortierungsalgorithmus ist eine rekursive Version der Einfügungssortierung, die Rekursion zum Sortieren von Arrays verwendet. Bei Subarrays der Größe 1 oder weniger werden sie als bereits sortiert betrachtet. Bei größeren Subarrays ruft es sich selbst rekursiv auf, um das Subarray ohne das letzte Element zu sortieren. Nachdem der rekursive Aufruf zurückgegeben und das Subarray sortiert wurde, platziert der Algorithmus das letzte Element an der richtigen Position im sortierten Subarray. Dies wird erreicht, indem das letzte Element mit den Elementen im sortierten Subarray verglichen und bei Bedarf nach rechts verschoben wird. Wiederholen Sie diesen Vorgang, bis alle Elemente an den richtigen Positionen eingefügt sind, was zu einem vollständig sortierten Array führt.

Beispiel

Die recursiveInsertionSort-Funktion wendet den Einfügungssortierungsalgorithmus rekursiv auf das Eingabearray an. Es prüft, ob das Array sortiert ist und gibt es zurück, wenn dies der Fall ist. Andernfalls ruft es sich selbst rekursiv auf einem Subarray der Größe n - 1 auf. Nach dem rekursiven Aufruf vergleicht die Funktion mithilfe einer While-Schleife das letzte Element mit den Elementen im sortierten Subarray. Ist ein Element größer, wird es nach rechts verschoben. Dieser Vorgang wird fortgesetzt, bis die Schleife den Anfang des Arrays erreicht oder ein kleineres Element gefunden wird. Abschließend wird das letzte Element an der richtigen Position eingefügt. Dieser Vorgang wird für alle Elemente wiederholt, sodass ein sortiertes Array entsteht.

function recursiveInsertionSort(arr, n = arr.length) {
   if (n <= 1) return arr;
 
   recursiveInsertionSort(arr, n - 1);
 
   let last = arr[n - 1];
   let j = n - 2;
 
   while (j >= 0 && arr[j] > last) {
      arr[j + 1] = arr[j];
      j--;
   }
 
   arr[j + 1] = last;
 
   return arr;
}
 
const arr = [9, 2, 7, 4, 1];
console.log(recursiveInsertionSort(arr));

Ausgabe

Das Folgende ist die Konsolenausgabe -

[ 1, 2, 4, 7, 9 ]

结论

最终，使用 JavaScript 实现插入排序算法以升序排列数字数组，对于寻求熟练排序方法的开发人员来说是一个精明的选择。通过迭代地将元素放置在适当的位置，该算法展示了一种组织数值数据的敏锐方法。虽然插入排序可能不像其他排序技术那样广受好评，但它的效率和简单性使其在某些情况下成为非常宝贵的工具。在 JavaScript 中使用此算法使开发人员能够在其编码库中使用鲜为人知但功能强大的工具，从而生成精简且有序的数组。总之，利用 JavaScript 中插入排序算法的强大功能，对于那些在数组排序中寻求精确性和优雅性的人来说，是一种不切实际的努力。

Das obige ist der detaillierte Inhalt vonImplementieren Sie die Einfügungssortierung mithilfe von JavaScript, um ein Array von Zahlen in aufsteigender Reihenfolge zu sortieren. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!