Idées de base
RadixSort est développé sur la base du tri du seau, et les deux tri sont des implémentations avancées de l'allocation de tri. L'idée de base de DistributivesOrt: le processus de tri ne nécessite pas de comparaison de mots clés, mais met en œuvre le tri à travers les processus "distribution" et "collecter". Leur complexité temporelle peut atteindre un ordre linéaire: o (n).
Le tri de la cardinalité est un algorithme de tri stable, mais a certaines limites:
1. Les mots clés peuvent être décomposés.
2. Le nombre de mots clés enregistrés est plus petit, et il vaut mieux s'ils sont denses. 3. S'il s'agit d'un nombre, il est préférable d'être non signé, sinon la complexité de cartographie correspondante sera augmentée. Vous pouvez d'abord les trier séparément.
Jetons un coup d'œil au tri du seau (radixsort).
Le tri du seau est également appelé tri des boîtes (Binsort). Son idée de base est de configurer plusieurs compartiments, de numériser les enregistrements à tri r [0], r [1],…, r [n-1], de charger tous les enregistrements avec des mots clés dans une certaine plage dans le kth bucket (alloué), puis de connecter les têtes et les queues de chaque seau non vide en séquence (collection) en fonction du numéro de séquence.
Par exemple, pour trier un 52 cartes à jouer mélangé par des points A <2 <… <j <q <k, 13 "seaux" doivent être définis. Lors du tri, chaque carte est placée dans le godet correspondant par des points, puis les seaux sont connectés en séquence pour obtenir un jeu de cartes disposé par ordre incrémentiel de points.
Dans le tri du seau, le nombre de seaux dépend de la plage de valeur du mot-clé. Par conséquent, le tri du godet nécessite que le type de mot-clé soit fini, sinon des seaux illimités peuvent être nécessaires.
D'une manière générale, il est imprévisible du nombre d'enregistrements avec les mêmes mots clés stockés dans chaque seau, de sorte que le type de seau doit être conçu comme une liste liée.
Pour s'assurer que le tri est stable, les connexions pendant le processus d'emballage et de collecte doivent être effectuées en fonction du premier principe de sortie.
Pour le tri du seau, le temps du processus d'allocation est O (n); L'heure du processus de collecte est O (m) (une liste liée est utilisée pour stocker l'entrée pour être des enregistrements triés) ou O (M + N). Par conséquent, le temps de tri du seau est O (M + N). Si l'ordre de grandeur du nombre de seaux m est O (n), le temps de tri du seau est linéaire, c'est-à-dire o (n).
La plupart du temps, la complexité des principaux algorithmes de tri mentionnés ci-dessus est O (N2), et certains algorithmes de tri sont O (nlogn). Mais le tri des barils peut atteindre la complexité du temps de O (n). Cependant, les inconvénients du tri du seau sont: tout d'abord, la complexité de l'espace est relativement élevée et les frais généraux supplémentaires sont nécessaires. Le tri a deux tableaux de surcharge d'espace, l'une stocke le tableau à tri, et l'autre est le soi-disant seau. Par exemple, la valeur à tri est de 0 à M-1, puis des seaux M sont nécessaires, et ce tableau de seau nécessite au moins un espace M. Deuxièmement, les éléments à tri doivent être dans une certaine plage, etc.
Le tri de la cardinalité est une amélioration du tri du seau, ce qui fait du "tri du seau" adapté à des ensembles plus grands de valeurs d'élément plutôt qu'à améliorer les performances.
Utilisons l'exemple des cartes à jouer pour illustrer. Une carte se compose de deux mots clés: costume (pêche <coeur <mei <carré) + valeur nominale (a <2 <3 <4 <... <k). Si la taille d'une carte est d'abord déterminée par la combinaison et que les cartes de la même combinaison sont déterminées par le numéro. Nous avons deux algorithmes pour résoudre ce problème.
Autrement dit, si les combinaisons sont différentes, quelle que soit la valeur nominale, la carte avec une couleur de combinaison inférieure est plus petite que la couleur du costume avec une couleur de costume plus élevée. Seulement dans la même couleur de combinaison, la relation de taille est déterminée par la taille de la valeur nominale. Il s'agit de la commande de plusieurs codes de clés.
Pour obtenir des résultats de tri, nous discutons de deux méthodes de tri.
Méthode 1: Triez d'abord les costumes et les couleurs et les divisez en 4 groupes, à savoir le groupe de fleurs de prune, le groupe carré, le groupe de cœur rouge et le groupe de cœur noir. Triez ensuite chaque groupe de groupes et enfin, connectez les 4 groupes ensemble.
Méthode 2: Tout d'abord, donnez 13 groupes de nombres (n ° 2, 3, ..., a) Selon 13 valeurs faciales, mettez les cartes dans les groupes de nombres correspondants dans l'ordre en fonction des valeurs faciales et divisez-les en 13 piles. Ensuite, donnez 4 groupes de numérotation (fleurs de prune, carrés, coeurs rouges, cœurs noirs), retirez les cartes du groupe 2 et les mettez dans le groupe de couleur correspondant, puis retirez les cartes du groupe 3 et les mettez dans le groupe de couleur correspondant, ... de cette façon, les 4 groupes de couleurs sont commandés en fonction de la valeur nominale, puis connectent les 4 groupes de couleurs en séquence.
Le tri de code multi-clé est trié dans l'ordre du code de clé principal au deuxième code de clé ou de la deuxième clé du code de clé principal, et est divisé en deux méthodes:
La méthode de priorité le plus significative (la plus significativedigitfirst), appelée méthode MSD:
1) Premier tri et les regrouper par K1, divisez la séquence en plusieurs sous-séquences. Dans les enregistrements du même groupe de séquences, les codes clés K1 sont égaux.
2) Triez ensuite chaque groupe en sous-groupes par K2. Après cela, continuez à trier les codes de clés suivants de cette manière jusqu'à ce que chaque sous-groupe soit trié par le code de clé le plus secondaire KD.
3) Connectez ensuite les groupes pour obtenir une séquence ordonnée. La méthode introduite dans les cartes de tri par costumes et valeurs faciales est la méthode MSD.
La méthode la moins importante de DigitFirst, appelée méthode LSD:
1) Commencez à trier à partir de KD, puis à trier KD-1, en répétant à son tour jusqu'à ce qu'il soit divisé en la plus petite sous-séquence selon K1.
2) Enfin, connectez chaque sous-séquence pour obtenir une séquence ordonnée. La deuxième méthode introduite dans les cartes de tri par costume et valeur nominale est la méthode LSD.
Un seul mot-clé d'un type numérique ou de caractères peut être considéré comme un mot multi-clé composé de plusieurs chiffres ou de plusieurs caractères. À l'heure actuelle, la méthode "allocation-collect" peut être utilisée pour la trier. Ce processus est appelé la méthode de tri de la cardinalité, où le nombre de valeurs possibles pour chaque nombre ou caractère est appelé la cardinalité. Par exemple, la base des combinaisons de cartes à jouer est 4 et la base de valeur nominale est de 13. Lors du tri des cartes à jouer, vous pouvez d'abord les organiser par le style ou par la valeur nominale. Lors du tri selon les couleurs, divisez-le d'abord en 4 piles (distributions) dans l'ordre du rouge, du noir, du carré et des fleurs, puis empilez-les (collectez) dans cet ordre, puis divisez-les en 13 piles (distributions) dans l'ordre de la valeur nominale, puis empilez-les (collecter) dans cet ordre. De cette façon, l'allocation et la collection secondaires peuvent organiser les cartes à jouer de manière ordonnée.
Pendant le processus "d'allocation-collection", la stabilité du tri doit être assurée.
L'idée du tri de la cardinalité est de se débarrasser de chaque groupe de mots clés dans les données à tri en séquence. Par exemple, la séquence suivante à tri:
135, 242, 192, 93, 345, 11, 24, 19
Nous divisons les singles, dix et centaines de chiffres de chaque valeur en trois mots clés, par exemple:
135-> K1 (chiffres à un seul) = 5, K2 (dix chiffres) = 3, K3 (cent chiffres) = 1.
Ensuite, commencez à partir du bit unique le plus bas (à partir du dernier mot-clé), tous les mots clés K1 de toutes les données sont alloués au seau (car chaque nombre est de 0 à 9, donc la taille du seau est 10), puis diffuse les données dans le seau en séquence pour obtenir la séquence suivante.
(11), (242, 192), (93), (24), (135, 345), (19) (tri à partir du mot clé le plus, ignorant les cent et dix chiffres, et allouant en fonction des numéros sur les chiffres à un seul))
Ensuite, la séquence ci-dessus est allouée pour K2, et la séquence de sortie est:
(11, 19), (24), (135), (242, 345), (192, 93) (reportez-vous au mot clé pour trier le deuxième mot-clé, ignorer les cent chiffres et allouer en fonction du numéro sur les dix chiffres)
Enfin, pour l'allocation du seau de K3, la séquence de sortie est:
(011, 019, 024, 093), (135, 192), (242), (345) (reportez-vous au deuxième mot-clé pour trier le mot-clé le plus élevé, ignorer les dix et les chiffres uniques et les attribuer en fonction des nombres sur les centaines de chiffres)
Le tri est complet.
Implémentation Java
public void radixSort () {int max = array [0]; for (int i = 0; i <array.length; i ++) {// Trouvez la valeur maximale dans le tableau if (array [i]> max) {max = array [i]; }} int keysNum = 0; // le nombre de mots clés, nous utilisons des chiffres uniques, dix chiffres et des centaines ... comme mots clés, donc le nombre de mots clés est le chiffre maximum while (max> 0) {max / = 10; keysNum ++; } List <ArrayList <Integer>> Buckets = new ArrayList <ArrayList <Integer >> (); pour (int i = 0; i <10; i ++) {// Le nombre possible pour chaque chiffre est 0 ~ 9, donc définir 10 buckets buckets.add (new ArrayList <Integer> ()); // Le godet est composé de ArrayList <Integer>} pour (int i = 0; i <keysNum; i ++) {// Commencez par le mot clé le plus récent, attribuez-le en fonction des mots clés à son tour pour (int j = 0; j <array.length; j ++) {// Scannez tous les éléments array comme 258. Vous devez maintenant supprimer le nombre sur les dix chiffres, 258% 100 = 58,58 / 10 = 5 int key = array [j]% (int) math.pow (10, i + 1) / (int) math.pow (10, i); Buckets.get (clé) .add (array [j]); // Mettez cet élément dans un seau avec la clé de mot-clé} // Après allocation, copiez les éléments du seau dans le tableau Int Counter = 0; // Counter d'élément pour (int j = 0; j <10; j ++) {ArrayList <Integer> Bucket = Buckets.get (J); // Bélleur avec mot-clé j while (bucket.size ()> 0) {array [compter ++] = Bucket.Remove (0); // Copiez le premier élément du seau dans le tableau et supprimez}} System.out.print ("Thread" + (i + 1) + "Wheel Sort:"); afficher(); }}Les résultats de l'impression sont les suivants:
Analyse d'algorithme
À première vue, l'efficacité d'exécution du tri de la cardinalité semble être bonne et il est incroyable que tout ce que vous avez à faire soit de copier les éléments de données d'origine du tableau à la liste liée, puis de les copier. S'il y a 10 éléments de données, il y a 20 réplications, répétant le processus pour chaque bit. En supposant que les nombres à 5 chiffres sont triés, 20 * 5 = 100 copies sont nécessaires. S'il y a 100 éléments de données, il y en a 200 * 5 = 1000 exemplaires. Le nombre de copies est proportionnel au nombre d'éléments de données, c'est-à-dire o (n). Il s'agit de l'algorithme de tri le plus efficace que nous ayons vu.
Malheureusement, plus il y a d'éléments de données, plus les mots clés sont nécessaires. Si les éléments de données sont augmentés de 10 fois, le mot-clé doit être ajouté par un (un autre cycle de tri). Le nombre de copies et le nombre d'éléments de données sont proportionnels à la longueur du mot clé, et il peut être considéré que la longueur du mot-clé est le logarithme de N.
Résumer
Ce qui précède est l'intégralité du contenu de cet article sur l'introduction au tri de la cardinalité et à l'implémentation de la langue Java. J'espère que ce sera utile à tout le monde. Les amis intéressés peuvent continuer à se référer à d'autres sujets connexes sur ce site. S'il y a des lacunes, veuillez laisser un message pour le signaler.