Qu'est-ce que le tri par base

Le tri par base est une généralisation du tri par compartiment. Les enregistrements qu'il considère comme triés contiennent plus d'un mot-clé ; le tri par base est un "tri distributif", qui utilise des informations partielles sur la valeur clé pour trier les enregistrements. Les éléments sont affectés à certains « compartiments » pour réaliser le tri. La méthode de tri par base est une méthode de tri stable.

Tri Radix

Le tri Radix est une généralisation du tri par compartiment, qui considère que les enregistrements de classement contiennent plus d'un mot-clé.

Introduction :

Le tri Radix est un « tri par distribution », également connu sous le nom de « tri par compartiment » ou tri par bac. Comme son nom l'indique, il s'agit d'informations partielles sur la valeur clé. les éléments à trier sont alloués à certains « compartiments » 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 la base prise. 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é.

Méthode de mise en œuvre

Méthode du premier chiffre le plus significatif, appelée méthode MSD : trier d'abord les groupes par k1, enregistrer dans le même groupe, le code clé k1 est égal, puis regrouper chacun Le groupe selon le tri k2 est divisé en sous-groupes, puis 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!