Beispiele zur Erläuterung einiger häufig verwendeter Sortieralgorithmen in JavaScript

JavaScript ist eine beliebte Programmiersprache, die zum Erstellen von Interaktivität auf Webseiten verwendet wird. Sortieren ist einer der wichtigsten Algorithmen in der Informatik, und auch das Sortieren in JavaScript ist eine Fähigkeit, die beherrscht werden muss. In diesem Artikel stellen wir einige häufig verwendete Sortieralgorithmen in JavaScript vor und zeigen, wie man sie implementiert.

1. Bubble Sort

Bubble Sort ist ein einfacher und intuitiver Sortieralgorithmus. Seine Grundidee besteht darin, jedes Mal zwei benachbarte Elemente zu vergleichen und ihre Positionen zu tauschen, wenn ihre Reihenfolge falsch ist. Nach jeder Sortierrunde wird das größte Element an das Ende des Arrays verschoben. Dieser Vorgang wird wiederholt, bis das gesamte Array sortiert ist.

Das Folgende ist die JavaScript-Implementierung der Blasensortierung:

function bubbleSort(arr) {
  var len = arr.length;
  for (var i = 0; i < len; i++) {
    for (var j = 0; j < len - i - 1; j++) {
      if (arr[j] > arr[j + 1]) {
        var temp = arr[j];
        arr[j] = arr[j + 1];
        arr[j + 1] = temp;
      }
    }
  }
  return arr;
}

Im obigen Code verwenden wir verschachtelte Schleifen, um benachbarte Elemente der Reihe nach zu vergleichen. Wenn das aktuelle Element größer als das nächste Element ist, tauschen wir ihre Positionen aus. Bei jedem Durchlauf der Schleife wird das größte Element an das Ende des Arrays verschoben. Die zeitliche Komplexität dieses Algorithmus beträgt O(n^2).

2. Auswahlsortierung

Auswahlsortierung ist ein weiterer einfacher Sortieralgorithmus. Seine Grundidee besteht darin, jedes Mal das kleinste Element im Array auszuwählen und es am Ende des sortierten Arrays zu platzieren. Die zeitliche Komplexität der Auswahlsortierung beträgt ebenfalls O(n^2).

Hier ist die JavaScript-Implementierung der Auswahlsortierung:

function selectionSort(arr) {
  var len = arr.length;
  for (var i = 0; i < len - 1; i++) {
    var minIndex = i;
    for (var j = i + 1; j < len; j++) {
      if (arr[j] < arr[minIndex]) {
        minIndex = j;
      }
    }
    if (minIndex !== i) {
      var temp = arr[i];
      arr[i] = arr[minIndex];
      arr[minIndex] = temp;
    }
  }
  return arr;
}

Im obigen Code verwenden wir zwei verschachtelte Schleifen, um den Mindestwert zu finden und ihn an das Ende des sortierten Arrays zu verschieben.

3. Einfügungssortierung

Einfügungssortierung ist ein einfacher, aber effizienter Sortieralgorithmus. Seine Grundidee besteht darin, ein zu sortierendes Element in eine bereits sortierte Reihenfolge einzufügen. Bei einer ungeordneten Folge beginnen wir immer mit dem ersten Element, nehmen von links nach rechts ein Element heraus und fügen es dann an der entsprechenden Position der geordneten Folge ein. Bis alle Elemente abgerufen sind, ist der Sortiervorgang abgeschlossen.

Das Folgende ist die JavaScript-Implementierung der Einfügungssortierung:

function insertionSort(arr) {
  var len = arr.length;
  var current, j;
  for (var i = 1; i < len; i++) {
    current = arr[i];
    j = i - 1;
    while (j >= 0 && arr[j] > current) {
      arr[j + 1] = arr[j];
      j--;
    }
    arr[j + 1] = current;
  }
  return arr;
}

Im obigen Code verwenden wir eine While-Schleife, um die sortierten Elemente nach rechts zu verschieben, um Platz für das Einfügen neuer Elemente zu schaffen. Die zeitliche Komplexität dieses Algorithmus beträgt O(n^2).

4. Schnellsortierung

Schnellsortierung ist ein häufig verwendeter und effizienter Sortieralgorithmus. Die Grundidee besteht darin, eine Basiszahl auszuwählen und alle Zahlen in der Folge mit dieser Basiszahl zu vergleichen. Platzieren Sie die Zahlen, die kleiner als die Basiszahl sind, links von der Basiszahl und die Zahlen, die größer als die Basiszahl sind, rechts von der Basiszahl und verarbeiten Sie dann die linken und rechten Teilsequenzen rekursiv.

Das Folgende ist die JavaScript-Implementierung der Schnellsortierung:

function quickSort(arr) {
  if (arr.length <= 1) return arr;
  var pivotIndex = Math.floor(arr.length / 2);
  var pivot = arr.splice(pivotIndex, 1)[0];
  var left = [];
  var right = [];
  for (var i = 0; i < arr.length; i++) {
    if (arr[i] < pivot) {
      left.push(arr[i]);
    } else {
      right.push(arr[i]);
    }
  }
  return quickSort(left).concat([pivot], quickSort(right));
}

Im obigen Code wählen wir zuerst eine Benchmark-Zahl aus, durchlaufen dann die gesamte Sequenz, fügen die Zahlen, die kleiner als die Benchmark-Zahl sind, in ein Array ein und fügen die Zahlen größer ein als die Benchmark-Nummer in ein Array in ein anderes Array. Schließlich verarbeiten wir die linken und rechten Arrays rekursiv und führen sie mit der Basiszahl zusammen. Die zeitliche Komplexität dieses Algorithmus beträgt O(nlogn).

Zusammenfassung

In diesem Artikel werden mehrere gängige Sortieralgorithmen und deren Implementierung in JavaScript vorgestellt. Ob Blasensortierung, Auswahlsortierung oder Einfügungssortierung, es handelt sich bei allen um sehr einfache und leicht verständliche Sortieralgorithmen, die für Anfänger zum Erlernen und Verstehen geeignet sind. Wenn Sie sich eingehender und umfassender mit Sortieralgorithmen befassen, können Sie auch versuchen, einige erweiterte Sortieralgorithmen zu verwenden, z. B. Zusammenführungssortierung, Heap-Sortierung usw.

Das obige ist der detaillierte Inhalt vonBeispiele zur Erläuterung einiger häufig verwendeter Sortieralgorithmen in JavaScript. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!