Algorithme de tri par fusion d'algorithme JavaScript (explication détaillée)

Dans cet article, nous apprenons la logique derrière le tri par fusion et l'implémentons en JavaScript. Enfin, le tri par fusion est comparé à d’autres algorithmes en termes de complexité spatiale et temporelle.

La logique derrière le tri par fusion

Le tri par fusion utilise le concept de diviser pour régner pour trier une liste d'éléments donnée. Il divise un problème en sous-problèmes plus petits jusqu'à ce qu'ils deviennent suffisamment simples pour être résolus directement.

Voici les étapes du tri par fusion :

1. Divisez la liste donnée en deux moitiés (si le nombre d'éléments dans la liste est impair, rendez-les à peu près égaux).

2. Continuez à diviser les sous-tableaux de la même manière jusqu'à ce qu'il ne reste qu'un seul tableau d'éléments.

3. À partir d'un seul tableau d'éléments, fusionnez les sous-tableaux afin de trier chaque sous-tableau fusionné.

4. Répétez l'étape 3 jusqu'à ce que vous obteniez enfin un tableau trié.

En prenant le tableau [4, 8, 7, 2, 11, 1, 3] comme exemple, voyons comment fonctionne le tri par fusion :

Utilisez JavaScript pour implémenter le tri par fusion

Implémentez d'abord une fonction qui fusionne deux sous-tableaux triés en un seul tableau triémerge(). Il est très important de noter que les deux sous-tableaux sont déjà triés et que la fonction merge() n'est utilisée que pour les fusionner. [Tutoriel recommandé : "Tutoriel vidéo JavaScript"]

peut être réalisé en parcourant ces deux sous-tableaux :

function merge(left, right) {
    let arr = []
    // 如果任何一个数组为空，就退出循环
    while (left.length && right.length) {
        // 从左右子数组的最小元素中选择较小的元素
        if (left[0] < right[0]) {
            arr.push(left.shift())  
        } else {
            arr.push(right.shift()) 
        }
    }
    
    // 连接剩余的元素，防止没有把两个数组遍历完整
    return [ ...arr, ...left, ...right ]
}

Dans cette fonction, en disposant les deux sous-tableaux triés (left, right) sont combinés pour obtenir un grand tableau trié. Tout d’abord, créez un tableau vide. Prenez ensuite le plus petit des plus petits éléments des deux sous-tableaux left et right et ajoutez-le au tableau vide. Il suffit de vérifier le premier élément des sous-tableaux left et right puisqu'ils sont triés.

Dans ce processus, l'élément sélectionné est supprimé du sous-tableau (implémenté par la fonction shift()). Continuez ce processus jusqu'à ce que l'un des sous-tableaux devienne vide. Enfin, insérez les éléments restants du sous-tableau non vide (car ils ont été triés) à la fin du tableau principal.

Maintenant que nous avons le code pour fusionner deux tableaux triés, voici le code final pour implémenter l'algorithme de tri par fusion. Cela signifie continuer à diviser le tableau jusqu'à ce que vous obteniez un tableau contenant un seul élément :

function mergeSort(array) {
  const half = array.length / 2
  
  if(array.length < 2){
    return array 
  }
  
  const left = array.splice(0, half)
  return merge(mergeSort(left),mergeSort(array))
}

Dans le code, déterminez d'abord le point médian et utilisez la fonction splice() pour diviser le tableau en deux sous-tableaux. Si le nombre d'éléments est impair, le nombre d'éléments à gauche sera un de moins. Continuez à diviser le tableau jusqu'à ce qu'il reste un tableau d'éléments uniques (array.length < 2). Fusionnez ensuite les sous-tableaux à l'aide de la fonction merge() implémentée précédemment.

Une fois le code implémenté, testez-le avec le cas d'utilisation précédent :

array = [4, 8, 7, 2, 11, 1, 3];
console.log(mergeSort(array));

Le résultat est conforme aux attentes :

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

Efficacité du tri par fusion

Le pire moment du tri par fusion La complexité est $O(n\log n)$, ce qui est la même que la complexité temporelle optimale du tri rapide. Le tri par fusion est l'un des algorithmes de tri les plus rapides actuellement disponibles.

Contrairement au tri rapide, le tri par fusion n'est pas un algorithme de tri sur place, ce qui signifie qu'il prend de l'espace supplémentaire en plus du tableau d'entrée. En effet, nous utilisons un tableau auxiliaire pour stocker les sous-tableaux. La complexité spatiale du tri par fusion est $O(n)$.

Un autre avantage du tri par fusion est qu'il est très adapté au multithreading, car chaque moitié divisée peut être triée indépendamment. Un autre moyen courant de réduire le temps d'exécution du tri par fusion consiste à utiliser le tri par insertion lorsque vous atteignez un sous-tableau relativement petit (environ 7 éléments). En effet, le tri par insertion fonctionne très bien avec des tableaux petits ou presque triés.

Résumé

Dans cet article, nous avons découvert la logique derrière l'algorithme Merge Sort et l'avons implémenté en JavaScript. C'est l'un des algorithmes de tri de base et peut nous aider à mieux comprendre la stratégie diviser pour régner.

Pour plus de connaissances liées à la programmation, veuillez visiter : Cours vidéo de programmation ! !

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!