Esiste un algoritmo di ordinamento intero O (n)?

L’ultima settimana sono incappato in questo articolo in cui gli autori menzionano nella seconda pagina:

Si noti che questo produce un tempo di esecuzione lineare per i pesi dei fronti interi.

Lo stesso nella terza pagina:

Ciò consente di ottenere un tempo di esecuzione lineare per i pesi dei fronti interi e O (m log n) per l’ordinamento basato sul confronto.

E all’ottava pagina:

In particolare, l’uso dell’ordinamento rapido potrebbe probabilmente accelerare notevolmente il GPA.

Questo significa che esiste un algoritmo di ordinamento O (n) in circostanze particolari per valori interi? O questa è una specialità della teoria dei grafi?

PS:
Potrebbe essere che il riferimento [3] potrebbe essere utile perché nella prima pagina dicono:

Ulteriori miglioramenti sono stati ottenuti per [..] classi di grafici come pesi con bordi interi [3], […]

ma non ho avuto accesso a nessuna delle riviste scientifiche.

Sì, l’ordinamento e il conteggio dei numeri radix sono O(N) . Non sono ordinamenti basati sul confronto, che hanno dimostrato di avere un limite inferiore Ω(N log N) .

Per essere precisi, l’ordinamento radix è O(kN) , dove k è il numero di cifre nei valori da ordinare. L’ordinamento di conteggio è O(N + k) , dove k è l’intervallo dei numeri da ordinare.

Esistono applicazioni specifiche in cui k è sufficientemente piccolo da consentire sia l’ordinamento di tipo di ordinamento digitale che quello di conteggio in tempo reale.

Gli ordinamenti di confronto devono essere almeno Ω (n log n) in media.

Tuttavia, contando la scala di ordinamento sort e radix linearmente con la dimensione dell’input – poiché non sono ordinamenti di confronto, sfruttano la struttura fissa degli input.

Ordinare il conteggio: http://en.wikipedia.org/wiki/Counting_sort se i numeri interi sono piuttosto piccoli. Radix sort se hai numeri più grandi (questa è fondamentalmente una generalizzazione del conteggio sort o un’ottimizzazione per i numeri più grandi, se vuoi): http://en.wikipedia.org/wiki/Radix_sort

C’è anche una sorta di benna: http://en.wikipedia.org/wiki/Bucket_sort

Sebbene non sia molto pratico (principalmente a causa dell’ampio overhead di memoria), ho pensato di menzionare Abacus (Bead) Sort come un altro algoritmo di ordinamento temporale lineare interessante.

Questi algoritmi di ordinamento basati su hardware:

Un algoritmo di ordinamento senza confronto
Ordinamento dei numeri binari nell’hardware – Un nuovo algoritmo e la sua implementazione

Laser Domino Sorting Algorithm : un esperimento mentale da me basato su Conteggio Sort con l’intento di raggiungere la complessità di tempo O(n) su Conteggio ordinamento O(n + k) .

Aggiungere un po ‘più di dettagli – Praticamente il miglior algoritmo di ordinamento fino alla data non è O (n), ma 0 (n \ sqrt {\ log \ log n}).

Puoi controllare ulteriori dettagli su questo algo nel documento: http://dl.acm.org/citation.cfm?id=652131