Radix est-il le seul algorithme de tri non comparaison?

Question

Comme le titre le dit, Radix Trier est-il le seul algorithme de tri non comparaison? Je suppose que c'est oui.

Answer 1

Non - il y a aussi le tri et le tri du seau, entre autres. Vérifier la Article Wikipedia pour plus d'informations.

Answer 2

Tout ensemble peut être trié en n'utilisant pas de comparaisons.

Le processus est

• Décidez d'une taille gérable du domaine d'entrée m que vous pouvez gérer pour enregistrer dans un tableau gérable. Pour Chars (8 bits), le domaine serait 0-255.
• Divisez l'entrée d'une manière ordonnée dans le tableau.
• Répétez et rincez si l'entrée n'est toujours pas complètement considérée, c'est-à-dire que tous les bits en m n'ont pas été pris en compte.

Par exemple, un type entier 32 bits, M pourrait être effectué comme:

• Regardez les 8 premiers bits, put (références, pointeurs ou ce que votre Lang a disponible), dans la gamme 8 bits. Mettez-les dans un tableau [0-255], vous avez maintenant une commande grossière (stade) de vos valeurs.
• Regardez les 8 bits suivants, placez-les dans un tableau similaire, gardez une référence à la première commande. Les 8x2 bits suivants sont traités de la même manière. Pour extraire, vous suivez les liens du premier ensemble.

Radix Sort utilise des chiffres et a 2 variantes, (MSB vers LSB) et (LSB à MSB).

Le rythme de comptage n'utilise que la première étape

Le tri du seau est généralement mentionné lors de la référence à un mélange de comptage et à une comparaison.

Fait intéressant, pour plusieurs cas d'utilisation, des triés de comparaison sont courts.