2 Exemples d'algorithme de tri Javascript Tri par fusion (Tri par fusion)

2 Exemples d'algorithme de tri Javascript Tri par fusion (Tri par fusion)_Connaissances de base

WBOY

Libérer： 2016-05-16 16:53:12

original

1111 Les gens l'ont consulté

La méthode de tri par fusion consiste à fusionner deux (ou plus) listes ordonnées en une nouvelle liste ordonnée, c'est-à-dire que la séquence à trier est divisée en plusieurs sous-séquences et chaque sous-séquence est ordonnée. Fusionnez ensuite les sous-séquences ordonnées dans la séquence ordonnée globale.

Le tri par fusion est un algorithme de tri efficace basé sur des opérations de fusion. Cet algorithme est une application très typique utilisant la méthode diviser pour régner (Divide and Conquer). 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.

Le processus d'opération de fusion est le suivant :

1. Demander de l'espace pour que sa taille soit la somme des deux séquences triées.
2 Définir deux pointeurs dont les positions initiales sont les deux séquences triées. Position de départ
3. Comparez les éléments pointés par les deux pointeurs, sélectionnez un élément relativement petit et placez-le dans l'espace de fusion, puis déplacez le pointeur vers la position suivante
4. Répétez l'étape 3 jusqu'à un certain pointeur atteint la fin de la séquence
5. Copiez tous les éléments restants de l'autre séquence directement à la fin de la séquence fusionnée

Exemple 1 :

Copier le code Le code est le suivant :

/**
 * L'opération de fusion (fusion), également appelée algorithme de fusion, fait référence à l'opération de fusion de deux séquences triées en une seule séquence. 
 * L'algorithme de tri par fusion repose sur des opérations de fusion. 
 *
 * Le processus d'opération de fusion est le suivant : 
 *
 * 1. Demandez de l'espace pour que sa taille soit la somme de deux séquences triées. Cet espace est utilisé pour stocker l'espace fusionné. séquence 
 * 2. Définissez deux pointeurs, les positions initiales sont les positions de départ des deux séquences triées 
 * 3. Comparez les éléments pointés par les deux pointeurs, sélectionnez l'élément relativement petit et placez-le dans la fusion espace, et déplacez le pointeur vers la position suivante 
 * 4. Répétez l'étape 3 jusqu'à ce qu'un pointeur atteigne la fin de la séquence 
 * 5. Copiez tous les éléments restants de l'autre séquence directement à la fin de la séquence fusionnée 
 *
*/

function mergeSort(items) {
 if (items.length < 2) {
 return items;
 }

 var middle = Math.floor(items.length / 2) ,
 left = items.slice(0, middle),
 right = items.slice(middle),
 params = merge(mergeSort(left), mergeSort(right));

 params.unshift(0, items.length);
 items.splice.apply(items, params);

 renvoyer les éléments;

 fonction de fusion (gauche, droite ) {
 var result = [],
 il = 0,
 ir = 0;

 while (il < left.length && ir < right.length) {
 if ( left[il] < right[ir]) {
                              result.push(left[il]); >                                                                                                                                       return result.concat(left.slice(il)) .concat(right.slice(ir) ); = [2, 1, 3, 12, 5, 66, 23, 87, 15, 32];

mergeSort(arr);




Exemple 2 : 






Copier le code

Le code est le suivant :