Tri en temps linéaire? [fermé]

Regardez radix tri.

Quand les gens disent "algorithme de tri", ils se réfèrent souvent à "algorithme de tri par comparaison", qui est tout algorithme qui ne dépend que de pouvoir demander"Est-ce que cette chose est plus grande ou plus petite que ça". Donc, si vous vous limitez à poser cette question sur les données, vous n'obtiendrez jamais plus de n*log(n) (c'est le résultat d'une recherche log(n) Des n ordres factoriels possibles d'un ensemble de données).

Si vous pouvez échapper aux contraintes de "comparison sort" et demander un plus question sophistiquée sur un morceau de données, par exemple "Quelle est la base 10 radix de ces données" alors vous pouvez trouver n'importe quel nombre d'algorithmes de tri du temps linéaire, ils prennent juste plus de mémoire.

C'est un compromis espace-temps. Le tri de Comparason prend peu ou pas de ram et s'exécute dans N * log (n) time. le tri radix (par exemple) s'exécute dans la mémoire O(N) time et o(log (radix)).

Wikipedia montre de nombreux algorithmes de tri différents et leurs complexités. vous pourriez vouloir vérifier

C'est vraiment simple, si n = 2 et les nombres sont uniques:

• Construisez Un tableau de bits (2^31-1 bits = > ~256MB). Les initialiser à zéro.
• Lisez l'entrée, pour chaque valeur que vous voyez, définissez le bit respectif dans le tableau sur 1.
• analysez le tableau, pour chaque jeu de bits, affichez la valeur respective.

Complexité = > O (2n)

Sinon, utilisez le tri Radix:

Complexité = > O (kn) (espérons-le)

Pensez aux nombres comme des nombres à trois chiffres où chaque chiffre varie de 0 à n-1. Trier ces nombres avec le tri radix. Pour chaque chiffre, il y a un appel au tri de comptage qui prend du temps Theta (n + n), de sorte que le temps d'exécution total correspond à Theta (n).

Un ensemble d'une plage limitée de nombres peut être représenté par un bitmap de bits de plage. Dans ce cas, un bitmap de 500 Mo, donc pour tout sauf des listes énormes, vous feriez mieux avec le tri Radix. Lorsque vous rencontrez le nombre k, définissez bitmap[k] = 1. Traversée unique à travers la liste, O (N).

Comme algo est possible:

M;// unsorted array
lngth; //number items of M
for(int i=0; i < lngth; i++)sorted[M[i]];

Il est seul possible algo pour la complexité linéaire, mais il a la complexité O (k*N) par ram (n-number array elements, K -- element's len)