Существует ли алгоритм сортировки по целому числу O (n)?
На прошлой неделе я наткнулся на эту статью, на которой авторы упомянут на второй странице:
Обратите внимание, что это дает линейное время работы для целочисленных весов ребер.
То же самое на третьей странице:
- Алгоритм естественной сортировки
- Что такое самоуверенное программное обеспечение?
- Алгоритм генерации анаграмм
- Для чего нужен пузырь?
- Как определить тип кредитной карты на основе номера?
Это дает линейное время работы для целочисленных весов ребер и O (m log n) для сортировки на основе сравнения.
И на 8-й странице:
В частности, использование быстрой цельной сортировки, вероятно, значительно ускорит GPA.
Означает ли это, что в особых случаях для целочисленных значений существует алгоритм сортировки O (n)? Или это специальность теории графов?
PS:
Может быть, ссылка [3] может быть полезна, потому что на первой странице они говорят:
Дальнейшие улучшения были достигнуты для classов графа [..], таких как целые веса ребер [3], […]
но у меня не было доступа к каким-либо научным журналам.
- Алгоритм для выделения перекрывающихся прямоугольников?
- Как вы находите точку на заданном перпендикулярном расстоянии от линии?
- Как измерить сходство между двумя изображениями?
- Как проверить, пересекает ли сегмент линии прямоугольник?
- Как работает переопределение переменных XOR?
- Сбита ли математика с плавающей запятой?
- Как найти пару с k-й наибольшей суммой?
- Лучший способ найти точку на круге, ближайшем к данной точке
Да, сортировка сортировки по методу и подсчету – O(N) . Они НЕ являются сравнительными сравнениями, которые, как оказалось, имеют нижнюю границу Ω(N log N) .
Если быть точным, сортировка по методу radix – это O(kN) , где k – количество цифр в сортируемых значениях. Сортировка сортировки – это O(N + k) , где k – диапазон номеров, подлежащих сортировке.
Существуют конкретные приложения, в которых k достаточно мало, что и сортировка сортировки и сортировки по методу radix демонстрирует линейную производительность на практике.
Сопоставления сортировки должны быть не менее Ω (n log n) в среднем.
Тем не менее, подсчет сортировки и сортировки по шкале оснований линейно с размером ввода – поскольку они не являются сортировками сортировки, они используют фиксированную структуру входов.
Подсчет сортировки: http://en.wikipedia.org/wiki/Counting_sort, если ваши целые числа довольно малы. Radix sort, если у вас есть большие числа (это в основном обобщение сортировки подсчета или оптимизация для больших чисел, если хотите): http://en.wikipedia.org/wiki/Radix_sort
Существует также сортировка ковша: http://en.wikipedia.org/wiki/Bucket_sort
Хотя это не очень практично (в основном из-за больших издержек памяти), я думал, что упомянул Abacus (Bead) Sort как еще один интересный алгоритм сортировки линейных времен.
Эти аппаратные алгоритмы сортировки:
Алгоритм сортировки без сравнения
Сортировка двоичных чисел в аппаратном обеспечении – новый алгоритм и его реализация
Алгоритм сортировки лазеров Domino – мысленный эксперимент, проведенный мной на основе Counting Sort с намерением достичь сложности времени O(n) по Counting Sort’s O(n + k) .
Добавление немного более подробной информации. Практически лучшим алгоритмом сортировки до даты является не O (n), а 0 (n \ sqrt {\ log \ log n}).
Вы можете узнать больше об этом алго в документе: http://dl.acm.org/citation.cfm?id=652131