Существует ли алгоритм целочисленной сортировки O (n)?

Question

На прошлой неделе я наткнулся на эту статью , где авторы упоминают на второй странице:

Обратите внимание, что это дает линейное время работы для целочисленных весов ребер.

То же самое на третьей странице:

Это дает линейное время работы для целочисленных весов ребер и O (m log n) для сортировки на основе сравнения.

А на 8-й странице:

В частности, использование быстрой целочисленной сортировки, вероятно, значительно ускорит GPA.

Означает ли это, что при особых обстоятельствах для целочисленных значений существует алгоритм сортировки O (n)? Или это специальность теории графов?

PS:
Может быть, что ссылка [3] может быть полезной, потому что на первой странице они говорят:

Дальнейшие улучшения были достигнуты для классов графов [..], таких как целочисленные ребра [3], [...]

но у меня не было доступа ни к одному из научных журналов.

Answer 1

Да, радикальная сортировка и счетная сортировка O(N). Они НЕ являются сортами, основанными на сравнении, которые, как доказывают, имеют Ω(N log N) нижнюю границу.

Если быть точным, радикальная сортировка равна O(kN), где k - количество цифр в значениях, подлежащих сортировке. Отсчет для сортировки: O(N + k), где k - диапазон чисел, подлежащих сортировке.

Существуют специальные приложения, где k достаточно мал, чтобы как сортировка по радиусу, так и сортировка по счету демонстрировали линейные характеристики на практике.

Answer 2

Сравнительные виды должны быть в среднем не менее Ω (n log n).

Тем не менее, сортировка при подсчете и сортировка по основанию масштабируется линейно с размером ввода & ndash; поскольку они не являются сравнительными, они используют фиксированную структуру входных данных.

Answer 3

Подсчет сортировки: http://en.wikipedia.org/wiki/Counting_sort, если ваши целые числа довольно малы. Корректировка сортировки, если у вас есть большие числа (это, в основном, обобщение счетной сортировки или оптимизация для больших чисел, если хотите): http://en.wikipedia.org/wiki/Radix_sort

Существует также сортировка ведра: http://en.wikipedia.org/wiki/Bucket_sort

Answer 4

Хотя это и не очень практично (в основном из-за большого объема памяти), я подумал, что упомяну Abacus (Bead) Sort в качестве другого интересного алгоритма линейной сортировки по времени.

Answer 5

Эти аппаратные алгоритмы сортировки:

Алгоритм сортировки без сравнения
Сортировка двоичных чисел в аппаратном обеспечении - новый алгоритм и его реализация

Лазерный алгоритм сортировки домино - мой мысленный эксперимент, основанный на подсчете сортировки с намерением достичь O(n) сложности по времени по сравнению с подсчетом сортировки O(n + k).

Answer 6

Добавление чуть более подробной информации - Практически лучший алгоритм сортировки до даты - это не O (n), а 0 (n \ sqrt {\ log \ log n}).

Подробнее об этом алгоритме вы можете узнать в статье: http://dl.acm.org/citation.cfm?id=652131