Le tri de fusion est un algorithme de tri efficace basé sur le fonctionnement de la fusion. Cet algorithme est une application très typique de la division et de la conquête.
La méthode de tri de fusion consiste à fusionner deux (ou plus de deux) des tables ordonnées dans une nouvelle table ordonnée, c'est-à-dire diviser la séquence à tri en plusieurs sous-séquences, chaque sous-séquence est ordonnée. Ensuite, les sous-séquences ordonnées sont combinées dans la séquence ordonnée globale.
Le tri de fusion est un algorithme de tri efficace basé sur le fonctionnement de la fusion. Cet algorithme est une application très typique de la division et de la conquête. Fusionner les sous-séquences ordonnées pour obtenir une séquence complètement ordonnée; Si deux tables ordonnées sont fusionnées dans une table ordonnée, elle est appelée fusion à 2 voies.
Le processus de fonctionnement de la fusion est le suivant:
1. Appliquer pour l'espace afin que sa taille soit la somme de deux séquences triées, qui est utilisée pour stocker les séquences fusionnées
2. Définir deux pointeurs, la position initiale est la position de départ des deux séquences triées respectivement
3. Comparez les éléments pointés par deux pointeurs, sélectionnez des éléments relativement petits et placez-les dans l'espace de fusion, 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 d'une autre séquence directement à la fin de la séquence de fusion
Exemple 1:
La copie de code est la suivante:
/ **
* La fusion, également connue sous le nom d'un algorithme de fusion, fait référence au fonctionnement de la combinaison de deux séquences triées en une seule séquence.
* L'algorithme de tri de fusion dépend de l'opération de fusion.
*
* Le processus de fonctionnement de la fusion est le suivant:
*
* 1. Appliquer l'espace afin que sa taille soit la somme de deux séquences triées, qui est utilisée pour stocker les séquences fusionnées
* 2. Définissez deux pointeurs, les positions initiales sont les positions de départ des deux séquences triées respectivement
* 3. Comparez les éléments pointés par les deux pointeurs, sélectionnez des éléments relativement petits et placez-les dans l'espace de fusion, 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 d'une autre séquence directement à la fin de la séquence fusionnée
*
* /
fonction fusionort (items) {
if (items.length <2) {
return les éléments;
}
var middle = math.floor (items.length / 2),
gauche = items.slice (0, milieu),
droit = items.slice (au milieu),
Params = Merge (Mergesort (gauche), Mergesort (à droite));
params.unshift (0, items.length);
items.splice.apply (éléments, params);
return les éléments;
fonction fusion (gauche, droite) {
var résultat = [],
il = 0,
ir = 0;
while (il <left.length && ir <droite.length) {
if (gauche [il] <droit [ir]) {
result.push (gauche [il ++]);
} autre {
résultat.push (à droite [IR ++]);
}
}
return result.concat (Left.slice (IL)) .Concat (droite.slice (ir));
}
}
// test
var arr = [2, 1, 3, 12, 5, 66, 23, 87, 15, 32];
Mergesort (ARR);
Exemple 2:
La copie de code est la suivante:
<script type = "text / javascript">
//Document.write("------------------------------------------ -------------------------------------------------- ----------------------------------------);
// Var Array = Nouveau tableau (12, 25, 32, 16, 18, 27, 59, 69, 36);
Var Count = 0;
// appelle la méthode de tri pour trier
// msort (tableau, array, 0, array.length - 1);
// Tableau source source
// Array Target dest
// S Démarrer l'indice
// indice ttarget
fonction msort (source, dest, s, t) {
var result = "";
var m;
var dest2 = new Array ();
if (s == t) {
dest [s] = source [s];
}
autre {
m = math.floor ((s + t) / 2);
msort (source, dest2, s, m);
msort (source, dest2, m + 1, t);
Merge (dest2, dest, s, m, t);
/ * Résultat de sortie * /
Résultat + = "<br /> Thread" + ++ Count + "Le résultat de l'ordre du PASS est:";
pour (var n = 0; n <dest.length; n ++) {
résultat + = array [n] + ",";
}
/ * Le résultat de sortie se termine * /
}
Résultat de retour;
}
/ * Le résultat de sortie se termine * /
// a fusionné deux tableaux dans l'ordre de petit à grand
// Source d'origine
// Array trié dest
// STHE premier indice
// m le tableau suivant du deuxième tableau
// longueur ntotale
Fonction Merge (Source, Dest, S, M, N) {
pour (var j = m + 1, k = s; j <= n && s <= m; k ++) {
if (source [s] <source [j]) {
dest [k] = source [s ++];
}
autre {
dest [k] = source [j ++];
}
}
// Ajouter les tableaux ordonnés restants à la fin du dest
if (s <= m) {
pour (var l = 0; l <= m - s; l ++) {
dest [k + l] = source [s + l];
}
}
if (j <= n) {
pour (var l = 0; l <= n - j; l ++) {
dest [k + l] = source [j + l];
}
}
}
//Document.write("<br /> <br /> ")
</cript>