In unseren vorherigen Artikeln haben wir eine ganze Reihe von Sortieralgorithmen wie Bubble Sort, Selection Sort und Insertion Sort kennengelernt. Wir haben gelernt, dass diese Sortieralgorithmen zwar sehr einfach zu implementieren sind, für gro?e Datens?tze jedoch nicht effizient sind, was bedeutet, dass wir einen effizienteren Algorithmus für die Sortierung gro?er Datens?tze und damit für die Zusammenführungssortierung ben?tigen. In dieser Serie gehen wir darauf ein, wie die Zusammenführungssortierung funktioniert und wie sie in JavaScript implementiert werden kann. Bist du bereit?

Inhaltsverzeichnis

1. Was ist der Zusammenführungssortierungsalgorithmus?
2. So funktionieren Zusammenführungssortierungsalgorithmen
   • Zeitkomplexit?t
   • Weltraumkomplexit?t
3. Implementierung in JavaScript
4. Fazit

Was ist der Merge-Sort-Algorithmus?

Merge Sort Algorithm ist ein ausgezeichneter Sortieralgorithmus, der dem Divide-and-Conquer-Prinzip folgt. Im Gegensatz zu einfacheren Algorithmen wie Selection Sort und Bubble Sort, die mehrere Durchg?nge durch das Array durchführen und benachbarte Elemente vergleichen, verfolgt Merge Sort einen strategischeren Ansatz:

1. Teilen: Zuerst teilt Merge Sort das Array in zwei H?lften
2. Erobern: Zweitens wird jede H?lfte rekursiv sortiert
3. Kombinieren: Zum Schluss werden die sortierten H?lften wieder zusammengefügt

Dieser Ansatz übertrifft durchweg einfachere O(n2)-Algorithmen wie Selection Sort und Bubble Sort, wenn es um gr??ere Datens?tze geht.

So funktionieren Zusammenführungssortierungsalgorithmen

Wir haben gesehen, dass die Zusammenführungssortierung mithilfe des beliebten Divide-and-Conquer-Ansatzes funktioniert. Unten finden Sie eine visuelle Darstellung der Funktionsweise.

Da wir nun die Magie gesehen haben, gehen wir durch die Funktionsweise des Merge-Sort-Algorithmus, indem wir dieses Array manuell sortieren: [38, 27, 43, 3, 9, 82, 10] mit dem oben genannten Ansatz.

Schritt 1: Teilen

Der erste Schritt bei der Zusammenführungssortierung besteht darin, das Array in Unterarrays zu unterteilen und dann jedes Unterarray in Unterarrays und das Unterarray in Unterarrays zu unterteilen, bis in allen Unterarrays nur noch ein Element übrig ist.

Schritt 2: Zurückverschmelzen (Erobern)

Der zweite Schritt besteht darin, mit dem Sortieren dieser Subarrays von Grund auf zu beginnen.

Zeitkomplexit?t

Merge Sort erreicht in allen F?llen (beste, mittlere und schlechteste) Zeitkomplexit?t von O(n log n) und ist damit für gr??ere Datens?tze effizienter als O(n2)-Algorithmen.

Hier ist der Grund:

• Dividieren: Das Array wird logarithmisch n-mal geteilt (jede Division halbiert die Gr??e)
• Zusammenführen: Jede Zusammenführungsebene erfordert n Operationen
• Gesamt: n Operationen × log n Ebenen = O(n log n)

Vergleichen Sie dies mit:

• Blasensortierung: O(n2)
• Auswahlsortierung: O(n2)
• Zusammenführungssortierung: O(n log n)

Für ein Array von 1.000 Elementen:

• O(n2) ≈ 1.000.000 Operationen
• O(n log n) ≈ 10.000 Operationen

Weltraumkomplexit?t

Merge Sort erfordert O(n) zus?tzlichen Speicherplatz, um die tempor?ren Arrays w?hrend des Zusammenführens zu speichern. Dies ist zwar mehr als der von Bubble Sort oder Selection Sort ben?tigte O(1)-Platz, aber die Zeiteffizienz macht diesen Kompromiss in der Praxis normalerweise lohnenswert.

Implementierung in JavaScript

// The Merge Helper Function
function merge(left, right) {
  const result = [];
  let leftIndex = 0;
  let rightIndex = 0;

  while (leftIndex < left.length && rightIndex < right.length) {
    if (left[leftIndex] <= right[rightIndex]) {
      result.push(left[leftIndex]);
      leftIndex++;
    } else {
      result.push(right[rightIndex]);
      rightIndex++;
    }
  }

  // Add remaining elements
  while (leftIndex < left.length) {
    result.push(left[leftIndex]);
    leftIndex++;
  }

  while (rightIndex < right.length) {
    result.push(right[rightIndex]);
    rightIndex++;
  }

  return result;
}

Aufschlüsselung der Zusammenführungsfunktion:

1. Funktionseinrichtung:

   const result = [];
   let leftIndex = 0;
   let rightIndex = 0;

• Erstellt ein leeres Array zum Speichern zusammengeführter Ergebnisse
• Initialisiert Zeiger für beide Eingabearrays
• Stellen Sie sich diese Zeiger wie Finger vor, die verfolgen, wo wir uns in jedem Array befinden

1. Hauptzusammenführungslogik:

   while (leftIndex < left.length && rightIndex < right.length) {
     if (left[leftIndex] <= right[rightIndex]) {
       result.push(left[leftIndex]);
       leftIndex++;
     } else {
       result.push(right[rightIndex]);
       rightIndex++;
     }
   }

• Vergleicht Elemente aus beiden Arrays
• Nimmt das kleinere Element und fügt es dem Ergebnis hinzu
• Bewegt den Zeiger in dem Array, aus dem wir entnommen haben, vorw?rts
• Als würde man beim Sortieren eines Stapels die kleinere von zwei Karten w?hlen

1. Aufr?umphase:

   while (leftIndex < left.length) {
     result.push(left[leftIndex]);
     leftIndex++;
   }

• Fügt alle verbleibenden Elemente hinzu
• Notwendig, da ein Array m?glicherweise l?nger ist als das andere
• Als würde man die restlichen Karten nach dem Vergleich einsammeln

Die Hauptfunktion zum Zusammenführen und Sortieren

function mergeSort(arr) {
  // Base case
  if (arr.length <= 1) {
    return arr;
  }

  // Divide
  const middle = Math.floor(arr.length / 2);
  const left = arr.slice(0, middle);
  const right = arr.slice(middle);

  // Conquer and Combine
  return merge(mergeSort(left), mergeSort(right));
}

MergeSort aufschlüsseln:

1. Basisfall:

   if (arr.length <= 1) {
     return arr;
   }

• Verarbeitet Arrays der L?nge 0 oder 1
• Diese sind bereits nach Definition sortiert
• Dient als unser Rekursionsstopppunkt

1. Teilungsphase:

   const middle = Math.floor(arr.length / 2);
   const left = arr.slice(0, middle);
   const right = arr.slice(middle);

• Teilt das Array in zwei H?lften
• Slice() erstellt neue Arrays, ohne das Original zu ?ndern
• Als würde man ein Kartenspiel in zwei H?lften schneiden

1. Rekursives Sortieren und Zusammenführen:

   return merge(mergeSort(left), mergeSort(right));

• Sortiert jede H?lfte rekursiv
• Kombiniert sortierte H?lften mithilfe der Zusammenführungsfunktion
• Zum Beispiel kleinere Kartenstapel zu sortieren, bevor man sie kombiniert

Beispiel-Komplettl?sung

Mal sehen, wie es sortiert wird [38, 27, 43, 3]:

1. Erster Split:

// The Merge Helper Function
function merge(left, right) {
  const result = [];
  let leftIndex = 0;
  let rightIndex = 0;

  while (leftIndex < left.length && rightIndex < right.length) {
    if (left[leftIndex] <= right[rightIndex]) {
      result.push(left[leftIndex]);
      leftIndex++;
    } else {
      result.push(right[rightIndex]);
      rightIndex++;
    }
  }

  // Add remaining elements
  while (leftIndex < left.length) {
    result.push(left[leftIndex]);
    leftIndex++;
  }

  while (rightIndex < right.length) {
    result.push(right[rightIndex]);
    rightIndex++;
  }

  return result;
}

1. Zweiter Split:

   const result = [];
   let leftIndex = 0;
   let rightIndex = 0;

1. Zurück zusammenführen:

   while (leftIndex < left.length && rightIndex < right.length) {
     if (left[leftIndex] <= right[rightIndex]) {
       result.push(left[leftIndex]);
       leftIndex++;
     } else {
       result.push(right[rightIndex]);
       rightIndex++;
     }
   }

Abschluss

Merge Sort zeichnet sich durch einen hocheffizienten Sortieralgorithmus aus, der bei gro?en Datens?tzen stets eine gute Leistung erbringt. Obwohl es im Vergleich zu einfacheren Sortieralgorithmen zus?tzlichen Platz ben?tigt, ist es aufgrund seiner O(n log n)-Zeitkomplexit?t eine erste Wahl für viele reale Anwendungen, bei denen die Leistung entscheidend ist.

Wichtige Erkenntnisse:

• Verwendet die Divide-and-Conquer-Strategie
• O(n log n) Zeitkomplexit?t in allen F?llen
• Ben?tigt O(n) zus?tzlichen Platz
• Stabiler Sortieralgorithmus
• Hervorragend geeignet für gro?e Datens?tze

Bleiben Sie auf dem Laufenden und verbunden

Um sicherzustellen, dass Sie keinen Teil dieser Serie verpassen und um mit mir in Kontakt zu treten, um mehr darüber zu erfahren
Diskussionen über Softwareentwicklung (Web, Server, Mobil oder Scraping/Automatisierung), Daten
Strukturen und Algorithmen und andere spannende Technologiethemen, folgen Sie mir auf:

Emmanuel Ayinde Folgen

Softwareentwickler | Technischer Redakteur | Backend-, Web- und Mobilentwickler? | Leidenschaft für die Entwicklung effizienter und skalierbarer Softwarel?sungen. #letsconnect ?

• GitHub
• Linkedin
• X (Twitter)

Bleiben Sie dran und viel Spa? beim Programmieren ????

Das obige ist der detaillierte Inhalt vonMerge-Sortieralgorithmus verstehen: Anf?ngerleitfaden zur Beherrschung des Sortieralgorithmus. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!