Introduction au tri par fusion en JavaScript (exemple de code)

Cet article vous apporte une introduction au tri par fusion en JavaScript (exemples de code). Il a une certaine valeur de référence. Les amis dans le besoin peuvent s'y référer.

Le tri par fusion (MERGE-SORT) est un algorithme de tri efficace basé sur des opérations de fusion. L'algorithme utilise la méthode diviser pour régner (pide). andConquer) est une application très typique. Fusionnez les sous-séquences déjà ordonnées pour obtenir une séquence complètement ordonnée ; c'est-à-dire que vous devez d'abord rendre chaque sous-séquence ordonnée, puis ordonner les segments de la sous-séquence. Si deux listes ordonnées sont fusionnées en une seule liste ordonnée, on parle de fusion bidirectionnelle.

Tri par fusion

Le tri par fusion est une méthode de tri très stable, et sa complexité temporelle est NlogN en termes de moyenne, de meilleur et de pire.

Deux étapes de tri par fusion

1. Diviser d'abord, jusqu'à ce qu'il n'y ait qu'un seul numéro

2. Split terminé Après cela, commencez le processus de fusion récursive

processus de division

Comme vous pouvez le voir sur la figure ci-dessus, le tri par fusion Will divisez un tableau en deux et arrêtez de le diviser lorsqu'il n'y a qu'un seul nombre.
Ensuite, le code de fractionnement est très simple, qui consiste à obtenir un pointeur q pointant vers le milieu et à diviser le tableau en deux parties : (start, p) et (p, end).

• p représente l'indice de début du tableau

• r représente l'indice de fin du tableau

    function pide(p, r){
        return Math.floor( (p + r) / 2 );
    }

Le processus de fusion

Le processus de fusion est comme indiqué dans l'image ci-dessus

1. Parcourez deux ensembles de données

2. Comparez les tailles

3. Sortez la plus petite valeur et mettez-la en première position

Par exemple :

• Supposons que les données du tableau A soient [2,5,1,3]

• Après notre démolition Après division, ce sera (0,2),(2,4);

• On passe A.slice(0,2) et A.slice(2 ,4)=> Obtenez deux tableaux A1[2,5] et A2[1,3]

• Ensuite on parcourt le tableau [2,5,1,3], le la première fois, nous obtiendrons Le plus petit nombre des deux côtés est 1, la deuxième fois est 2, la troisième fois est 3 et la quatrième fois est 5

    function merge(A, p, q, r){
        const A1 = A.slice(p, q);
        const A2 = A.slice(q, r);
        
        // 哨兵，往A1和A2里push一个最大值，比如防止A1里的数都比较小，导致第三次遍历某个数组里没有值
        
        A1.push(Number.MAX_SAFE_INTEGER);
        A2.push(Number.MAX_SAFE_INTEGER);
        // 循环做比较，每次取出较小的那个值
        for (let i = p, j = 0, k = 0; i <h3 id="Programme-principal">Programme principal</h3><p></p><pre class="brush:php;toolbar:false">    function merge_sort(A, p = 0, r) {
      r = r || A.length;
      if (r - p === 1) {
        return;
      }
      const q = pide(p, r);
      merge_sort(A, p, q);
      merge_sort(A, q, r);
      merge(A, p, q, r);
    
      return A;
    }

Programme principal

    function pide(p, r) {
      return Math.floor((p + r) / 2);
    }
    
    function merge(A, p, q, r) {
      const A1 = A.slice(p, q);
      const A2 = A.slice(q, r);
      A1.push(Number.MAX_SAFE_INTEGER);
      A2.push(Number.MAX_SAFE_INTEGER);
    
      for (let i = p, j = 0, k = 0; i Le programme principal est de faire de la récursion Répétez l'opération ci-dessus<p class="comments-box-content"></p>Code complet

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!