A quoi sert le tri par fusion ?

Le tri par fusion est un algorithme de tri efficace basé sur l'opération de fusion. Il peut être utilisé pour trier le désordre global mais les sous-éléments sont relativement ordonnés, et pour trouver le logarithme inverse. le processus de fusion, le logarithme inverse de chaque petit intervalle est calculé, puis le logarithme inverse du grand intervalle est calculé.

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) 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. Le tri par fusion est une méthode de tri stable.

Objectif

Tri

(La vitesse est juste derrière le tri rapide, c'est un tri stable algorithme, généralement utilisé. Pour un enchaînement généralement désordonné mais chaque sous-élément est relativement ordonné, merci de vous référer à la procédure standard de la Question 3 "Tour Suisse" des Demi-Finales Populaires 2011)

Trouver le logarithme inverse

L'idée spécifique est de calculer le logarithme inverse de chaque petit intervalle pendant le processus de fusion, puis de calculer le logarithme inverse du grand intervalle (il peut également être résolu à l'aide d'un arbre tableau)

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!