A quoi sert le tri par base ?

Le tri Radix est un "tri distributif". Il alloue les éléments à trier à certains "seaux" via une partie des informations de valeur clé pour obtenir l'effet de tri adapté au tri des données telles que l'heure. et une ficelle dont le poids total est inconnu.

Le tri Radix est un "tri par distribution", également appelé "tri par compartiment" ou tri par bac Comme son nom l'indique, il alloue les éléments à trier. dans certains « compartiments » via une partie des informations de valeur clé pour obtenir l'effet de tri. La méthode de tri par base est un tri stable, et sa complexité temporelle est O (nlog (r) m), où r est la base prise, et m. est le nombre de tas. À certains moments, la méthode de tri par base est plus efficace que les autres méthodes de tri par stabilité.

Le tri Radix convient au tri de données telles que l'heure et les chaînes dont le poids global est inconnu.

Méthode de mise en œuvre

Méthode du premier chiffre le plus significatif, dite méthode MSD : premier tri et regroupement par k1, enregistrement dans le même groupe, saisie Si les codes k1 sont égaux, puis chaque groupe est trié en sous-groupes selon k2. Après cela, les codes clés suivants continuent d'être triés et regroupés de cette manière jusqu'à ce que chaque sous-groupe soit trié selon le code clé kd le plus bas. Connectez ensuite les groupes pour obtenir une séquence ordonnée.

Première méthode du chiffre le moins significatif, appelée méthode LSD : commencez à trier à partir de kd, puis triez kd-1, répétez en séquence jusqu'à ce que k1 soit trié et qu'une séquence ordonnée soit obtenue.

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!