Explication détaillée du tri par fusion en JavaScript

Cet article parle du tri par fusion en JavaScript. Si vous ne connaissez pas le tri par fusion en JavaScript ou si vous êtes intéressé par le tri par fusion en JavaScript, jetons un coup d'œil à cet article. Bon, sans plus tarder, passons à cela. le point. Bar

Tri par fusion en JavaScript

En tant qu'application algorithmique typique de l'idée diviser pour régner, la mise en œuvre de la fusion le tri se compose de deux méthodes :

1. Récursivité descendante (toutes les méthodes récursives peuvent être réécrites par itération, il existe donc la deuxième méthode)

2. Itération ascendante

Dans "Description de la structure des données et de l'algorithme JavaScript", l'auteur donne une méthode d'itération ascendante. Mais pour la méthode récursive, l'auteur pense :

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

Pour être honnête, je ne comprends pas bien cette phrase. Cela signifie-t-il que la mémoire du compilateur JavaScript est trop petite et que la récursivité est trop profonde, ce qui peut facilement provoquer un débordement de mémoire ? J'espère que quelqu'un pourra me donner quelques conseils.

Comme le tri par sélection, les performances du tri par fusion ne sont pas affectées par les données d'entrée, mais les performances sont bien meilleures que celles du tri par sélection car la complexité temporelle est toujours O(n log n). Le prix est un espace mémoire supplémentaire.

Démonstration d'animation de tri par fusion

Implémentation du code JavaScript de tri par fusion :

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;}

Ce qui précède est tout le contenu de cet article, Si vous n’y connaissez pas encore grand-chose, vous pouvez facilement le maîtriser en mettant davantage en œuvre les deux côtés !

Recommandations associées :

Question intéressante JavaScript : fusionner le tri des listes liées

JavaScript implémente l'insertion de listes chaînées tri et tri par fusion de liste chaînée

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!