sorte radix sur les chaînes binaires de longueur arbitraire

Question

i googlé et voir beaucoup de discussions au sujet de tri radix sur chaîne binaire, mais ils sont tous avec la même longueur, comment aobut chaîne binaire avec longueur arbitraire?

dire que j'ai { "001", "10101", "011010", "10", "111"}, comment dois-je faire sur eux sorte radix? Merci!

Answer 1

Trouvez la longueur maximale et remplissez-les tous à cette longueur. Devrait encore bien fonctionner à condition qu'il y ait une limite supérieure sur la longueur de la plus longue chaîne.

Answer 2

Vous pouvez les remplir tous pour avoir la même longueur, mais il n'y a aucune raison réelle d'exécuter un algorithme de tri pour déterminer qu'un nombre de longueur 5 en binaire est plus long qu'une longueur 2 un. Vous obtiendrez probablement de meilleures performances en regroupant les nombres par longueur et en exécutant votre tri radix dans chaque groupe. Bien sûr, cela dépend de la façon dont vous les regroupez, puis de la façon dont vous triez vos groupes.

Un exemple de la façon dont vous pourriez faire serait de courir à travers tous les articles une fois tous les jeter dans une table de hachage (longueur -> numéros de cette longueur). Cela prend un temps linéaire, puis disons le temps nlogn pour y accéder dans l'ordre. Un tri radix s'exécute en O (nk) où n est le nombre d'éléments et k est leur longueur moyenne. Si vous avez un grand k, alors la différence entre O (nk) et O (nlogn) serait acceptable.

Answer 3

Si la création d'une tonne de nouvelles occurrences de chaîne laisse un mauvais goût, écrivez vous-même la comparaison.

Comparez ce que les longueurs des cordes seraient sans le 0 de (c.-à-trouver le firstIndexOf("1").); la chaîne la plus longue est plus grande.
Si les deux ont la même longueur, continuez de les comparer, caractère par caractère, jusqu'à ce que vous trouviez deux caractères différents - la chaîne avec le "1" est la plus grande.