Que signifie le tri par fusion ?

Le tri par fusion est un algorithme de tri efficace basé sur l'opération de fusion. Il fusionne des sous-séquences ordonnées pour obtenir une séquence complètement ordonnée. Cet algorithme utilise la méthode diviser pour régner. L'opération de fusion, également appelée algorithme de fusion, fait référence à la méthode de fusion de deux séquences séquentielles en une seule séquence séquentielle.

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 (Divider et conquérir). ) est une application très typique.

Fusionnez les sous-séquences ordonnées pour obtenir une séquence complètement ordonnée ; c'est-à-dire, rendez d'abord chaque sous-séquence ordonnée, puis ordonnez les segments de la sous-séquence.

Si deux listes ordonnées sont fusionnées en une seule liste ordonnée, cela s'appelle une fusion bidirectionnelle. Le tri par fusion est une méthode de tri stable.

L'opération de fusion (fusion), également appelée algorithme de fusion, fait référence à la méthode de fusion de deux séquences séquentielles en une seule séquence séquentielle.

Exemple

Il existe une séquence {6, 202, 100, 301, 38, 8, 1}

État initial : 6,202,100,301,38,8, 1

Après la première fusion : {6,202}, {100,301}, {8,38}, {1}, nombre de comparaisons : 3

Après la deuxième fusion : {6,100,202,301} , {1,8,38}, nombre de comparaisons : 4 ;

Après la troisième fusion : {1,6,8,38,100,202,301}, nombre de comparaisons :

Comparaison totale Le nombre de fois est : 3+4+4=11 ;

Le nombre inversé est 14

Pour plus de connaissances connexes, veuillez visiter le Site Web PHP chinois ! !

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!