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

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

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

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

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

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

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

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

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

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

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

Ответ 1

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

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

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

Ответ 2

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

Однако подсчет сортировки и радиальная сортировка шкала линейно с размером ввода – потому что они не являются сортировками сортировки, они используют фиксированную структуру входов.

Ответ 3

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

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

Ответ 4

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

Ответ 5

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

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

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

Ответ 6

Добавим немного больше деталей. Практически лучший алгоритм сортировки до даты - это не O (n), а O (n & radic; (log log n)) ожидаемое время.

Вы можете проверить более подробную информацию об этом алгоритме в Yijie Han & Бумага Mikkel Thorup FOCS '02.

Ответ 7

Да, существует алгоритм сортировки O (n), мы можем использовать алгоритм быстрой сортировки, чтобы получить эту сложность.