Существует ли алгоритм сортировки по целому числу 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), мы можем использовать алгоритм быстрой сортировки, чтобы получить эту сложность.
