Ausführliche Erläuterung der Zusammenführungssortierung in JavaScript

In diesem Artikel geht es um die Zusammenführungssortierung in JavaScript. Wenn Sie sich mit der Zusammenführungssortierung in JavaScript nicht auskennen, schauen wir uns diesen Artikel ohne weitere Umschweife an Der Punkt. Bar

Merge-Sortierung in JavaScript

Als typische Algorithmusanwendung der Divide-and-Conquer-Idee die Implementierung von Merge sort besteht aus zwei Methoden:

1. Top-Down-Rekursion (alle rekursiven Methoden können durch Iteration umgeschrieben werden, daher gibt es die zweite Methode)

2. Bottom-up-Iteration

In „Data Structure and Algorithm JavaScript Description“ gibt der Autor eine Bottom-up-Iterationsmethode an. Aber für die rekursive Methode denkt der Autor:

However, it is not possible to do so in JavaScript, as the recursion goes too deep for the language to handle.
然而,在 JavaScript 中这种方式不太可行,因为这个算法的递归深度对它来讲太深了。

Um ehrlich zu sein, verstehe ich diesen Satz nicht ganz. Bedeutet das, dass der Speicher des JavaScript-Compilers zu klein und die Rekursion zu tief ist, was leicht zu einem Speicherüberlauf führen kann? Ich hoffe, jemand kann mir einen Rat geben.

Wie bei der Auswahlsortierung wird die Leistung der Zusammenführungssortierung nicht durch die Eingabedaten beeinflusst, aber die Leistung ist viel besser als bei der Auswahlsortierung, da die zeitliche Komplexität immer O(n log n) ist. Der Preis ist zusätzlicher Speicherplatz.

Demonstration der Animation zum Zusammenführen der Sortierung

Implementierung des JavaScript-Codes zum Zusammenführen der Sortierung:

function mergeSort(arr) {  //采用自上而下的递归方法  
   var len = arr.length;  
   if(len < 2) {  
       return arr;  
   }  
   var middle = Math.floor(len / 2),  
       left = arr.slice(0, middle),  
       right = arr.slice(middle);  
   return merge(mergeSort(left), mergeSort(right));}function merge(left, right){  
   var result = [];  
  
   while (left.length && right.length) {  
       if (left[0] <= right[0]) {  
           result.push(left.shift());  
       } else {  
           result.push(right.shift());  
       }  
   }  
  
   while (left.length)  
       result.push(left.shift());  
  
   while (right.length)  
       result.push(right.shift());  
  
   return result;}

Das Obige ist der gesamte Inhalt dieses Artikels. Wenn Sie noch nicht viel darüber wissen, können Sie es leicht meistern, indem Sie mehr von beiden Seiten implementieren!

Verwandte Empfehlungen:

JavaScript Interessante Frage: Art verknüpfter Listen zusammenführen

JavaScript implementiert das Einfügen verknüpfter Listen Sortierung und Zusammenführung verknüpfter Listen

Das obige ist der detaillierte Inhalt vonAusführliche Erläuterung der Zusammenführungssortierung in JavaScript. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!