Comment trier ces éléments en temps o (n)?

Question

Disons donc que j'ai un éventail d'éléments où chacune des valeurs peut aller de 0 à $ n ^ 2-1 $. J'essaie de créer un algorithme pour trier ce tableau en temps de fonctionnement O (n) et je pensais utiliser le tri Radix. Le temps d'exécution du tri Radix est o (d (n + n)) ou o (dn) si n est vraiment grand. Alors, comment puis-je modifier le tri Radix pour qu'il fonctionne en o (n)?

Edit: Je ne pense pas que vous compreniez cela. La quantité d'éléments dans le tableau est n mais la valeur réelle pour chaque élément peut varier de 0 à n ^ 2 - 1. Donc, si nous avons un tableau avec 10 éléments, alors le plus grand élément peut être 99 et le plus petit Il peut être 0 mais il y aura encore 10 éléments dans le tableau.