Существует ли O (n) целочисленный алгоритм сортировки?
На прошлой неделе я споткнулся данную статью, где авторы упоминают на второй странице:
Обратите внимание, что это приводит к линейному времени выполнения для целочисленного веса ребра.
То же на третьей странице:
Это приводит к линейному времени выполнения для целочисленного веса ребра, и O (m регистрируют n) для основанной на сравнении сортировки.
И на 8-й странице:
В частности, использование быстрой целочисленной сортировки, вероятно, значительно ускорило бы GPA.
Это означает, что существует O (n) сортировка алгоритма при особых обстоятельствах для целочисленных значений? Или действительно ли это - специальность теории графов?
PS:
Могло случиться так, что ссылка [3] могла быть полезной, потому что на первой странице они говорят:
Дальнейшее совершенствование было достигнуто для [..] классы графика, такие как целочисленный вес ребра [3], [...]
но у меня не было доступа ни к одному из научных журналов.
4 ответа
Да, сортировка по основанию и подсчету O (N) . Это НЕ основанные на сравнении сортировки, которые, как было доказано, имеют нижнюю границу Ω (N log N) .
Чтобы быть точным, сортировка по основанию системы счисления равна O (kN) , где k - количество цифр в значениях, которые необходимо отсортировать. Сортировка с подсчетом O (N + k) , где k - это диапазон сортируемых чисел.
Существуют определенные приложения, в которых k достаточно мало, чтобы на практике как поразрядная, так и подсчетная сортировка демонстрировали линейную производительность.
Сортировки сравнения должны быть в среднем не менее Ω (n log n).
Однако сортировка с подсчетом и поразрядная сортировка масштабируются линейно с размером входных данных - поскольку они не являются сортировками для сравнения, они используют фиксированную структуру входных данных.
Хотя это не очень практично (в основном из-за больших накладных расходов на память), я подумал, что упомянул бы Abacus (Bead) Sort как еще один интересный алгоритм линейной сортировки по времени.
Счетная сортировка: http://en.wikipedia.org/wiki/Counting_sort, если ваши целые числа достаточно малы. Радиксная сортировка, если у вас большие числа (по сути, это обобщение счетной сортировки, или оптимизация для больших чисел, если хотите): http://en.wikipedia.org/wiki/Radix_sort
Существует также сортировка по ведрам: http://en.wikipedia.org/wiki/Bucket_sort