Erfahren Sie, wie Sie die Zusammenführungssortierung mit JavaScript implementieren

javascriptColumn In diesem Artikel lernen wir die Logik hinter Merge Sort kennen und implementieren sie in JavaScript. Abschließend wird die Zusammenführungssortierung hinsichtlich der räumlichen und zeitlichen Komplexität mit anderen Algorithmen verglichen.

Empfohlen (kostenlos): JavaScript (Video)

Die Logik hinter der Zusammenführungssortierung

Die Zusammenführungssortierung verwendet das Konzept von Teile und herrsche, um eine bestimmte Liste von Elementen zu sortieren. Dabei wird das Problem in kleinere Teilprobleme zerlegt, bis diese einfach genug sind, um direkt gelöst zu werden.

Hier sind die Schritte für die Zusammenführungssortierung:

1. Teilen Sie die gegebene Liste in zwei Hälften (wenn die Liste eine ungerade Anzahl von Elementen hat, machen Sie sie ungefähr gleich).
2. Fahren Sie mit der Aufteilung der Unterarrays auf die gleiche Weise fort, bis nur noch ein einziges Elementarray übrig bleibt.
3. Ausgehend von einem einzelnen Elementarray fügt Unterarrays zusammen, sodass jedes zusammengeführte Unterarray sortiert wird.
4. Wiederholen Sie Schritt 3, bis Sie endlich ein sortiertes Array erhalten.

Am Beispiel des Arrays [4, 8, 7, 2, 11, 1, 3] sehen wir uns an, wie die Zusammenführungssortierung funktioniert: [4, 8, 7, 2, 11, 1, 3] 为例，让我们看一下归并排序是如何工作的：

用 JavaScript 实现归并排序

首先实现一个将两个已排序子数组合并为一个已排序数组的函数 merge() 。要注意着两个子数组是已经被排好序的，这一点非常重要， merge() 函数只用于其进行合并。

可以通过遍历这两个子数组来实现：

function merge(left, right) {
    let arr = []
    // 如果任何一个数组为空，就退出循环
    while (left.length && right.length) {
        // 从左右子数组的最小元素中选择较小的元素
        if (left[0] <p>在这个函数中，通过把两个排好序的子数组（<code>left</code>、<code>right</code>）合并来获得一个排好序的大数组。首先，创建一个空数组。之后在 <code>left</code> 和 <code>right</code> 两个子数组中最小元素中的较小的一个，并将其添加到空数组。我们只需要检查 <code>left</code> 和 <code>right</code> 子数组中的第一个元素，因为它们是已排好序的。</p><p>在这个过程中，从子数组中删除了被选择的元素（通过 <code>shift()</code>  函数实现）。继续这个过程，直到其中一个子数组变为空。最后把非空子数组的剩余元素（因为它们已经被排序）插入主数组的最后面。</p><p>现在有了合并两个已排序数组的代码，接下来为实现归并排序算法的最终代码。这意味着要继续分割数组，直到最终只包含一个元素的数组为止：</p><pre class="brush:php;toolbar:false">function mergeSort(array) {
  const half = array.length / 2
  
  if(array.length <p>在代码中先确定中点，并用 <code>splice()</code> 函数将数组分为两个子数组。如果元素数量为奇数，则左侧的元素数量会少一个。不断的划分数组，直到剩下单个元素的数组（<code>array.length ）。然后用之前实现的 <code>merge()</code></code></p><img src="https:%20/%20/img.php.cn/upload/image/267/126/337/1609753127774293.png" title="1609753127774293.png" alt="Erfahren Sie, wie Sie die Zusammenführungssortierung mit JavaScript implementieren"><p></p><p>Verwenden Sie JavaScript Zusammenführungssortierung implementieren </p><p><strong>Erste Implementierung eine Funktion <code>merge()</code>, die zwei sortierte Unterarrays zu einem einzigen sortierten Array zusammenführt. Es ist wichtig zu beachten, dass die beiden Subarrays bereits sortiert sind und die Funktion <code>merge()</code> nur zum Zusammenführen verwendet wird. </strong></p>Kann durch Durchlaufen dieser beiden Unterarrays erreicht werden: <p></p><pre class="brush:php;toolbar:false">array = [4, 8, 7, 2, 11, 1, 3];
console.log(mergeSort(array));

In dieser Funktion werden die beiden sortierten Unterarrays (links, rechts) zusammengeführt, um ein zu erhalten sortiertes großes Array. Erstellen Sie zunächst ein leeres Array. Nehmen Sie dann das kleinere der kleinsten Elemente in den beiden Unterarrays left und right und fügen Sie es dem leeren Array hinzu. Wir müssen nur das erste Element in den Subarrays left und right überprüfen, da diese bereits sortiert sind.

Bei diesem Vorgang wird das ausgewählte Element aus dem Subarray gelöscht (implementiert durch die Funktion shift()). Setzen Sie diesen Vorgang fort, bis eines der Subarrays leer ist. Fügen Sie abschließend die verbleibenden Elemente des nicht leeren Unterarrays (da sie sortiert wurden) am Ende des Hauptarrays ein.

Da wir nun den Code zum Zusammenführen zweier sortierter Arrays haben, ist hier der endgültige Code zum Implementieren des Sortieralgorithmus zum Zusammenführen. Das bedeutet, dass Sie das Array weiter aufteilen, bis Sie am Ende ein Array haben, das nur ein Element enthält:

1,2,3,4,7,8,11

Bestimmen Sie im Code zunächst den Mittelpunkt und verwenden Sie die Funktion splice(), um das Array in zwei Unterarrays aufzuteilen . Wenn die Anzahl der Elemente ungerade ist, ist die Anzahl der Elemente auf der linken Seite um eins geringer. Teilen Sie das Array kontinuierlich, bis ein Array aus einzelnen Elementen übrig bleibt (array.length ). Führen Sie dann die Subarrays mit der zuvor implementierten Funktion <code>merge() zusammen.

Nachdem der Code implementiert wurde, testen Sie ihn mit dem vorherigen Anwendungsfall: rrreee

Die Ausgabe entspricht den Erwartungen:

rrreee

🎜Effizienz der Zusammenführungssortierung🎜🎜🎜Die schlechteste Zeitkomplexität der Zusammenführungssortierung beträgt $O(n \log n)$ und die beste Zeitkomplexität von Quicksort ist gleich. Merge Sort ist einer der schnellsten derzeit verfügbaren Sortieralgorithmen. 🎜🎜Im Gegensatz zur Schnellsortierung ist die Zusammenführungssortierung kein 🎜In-Place-Sortieralgorithmus, was bedeutet, dass sie zusätzlich zum Eingabearray zusätzlichen Platz beansprucht. Dies liegt daran, dass wir ein Hilfsarray zum Speichern von Unterarrays verwenden. Die räumliche Komplexität der Zusammenführungssortierung beträgt $O(n)$. 🎜🎜Ein weiterer Vorteil der Zusammenführungssortierung besteht darin, dass sie sich sehr gut für Multithreading eignet, da jede geteilte Hälfte unabhängig sortiert werden kann. Eine weitere übliche Möglichkeit, die Laufzeit der Zusammenführungssortierung zu verkürzen, besteht darin, die Einfügungssortierung zu verwenden, wenn Sie ein relativ kleines Subarray (ca. 7 Elemente) erreichen. Dies liegt daran, dass die Einfügungssortierung sehr gut mit kleinen oder nahezu sortierten Arrays funktioniert. 🎜🎜🎜Zusammenfassung🎜🎜🎜In diesem Artikel haben wir die Logik hinter dem Merge-Sort-Algorithmus kennengelernt und ihn in JavaScript implementiert. Es ist einer der grundlegenden Sortieralgorithmen und kann uns helfen, die Divide-and-Conquer-Strategie besser zu verstehen. 🎜

Das obige ist der detaillierte Inhalt vonErfahren Sie, wie Sie die Zusammenführungssortierung mit JavaScript implementieren. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!