Алгоритм сортировки, который выполняется за время O (n), а также сортирует по месту

Question

Есть ли какой-нибудь алгоритм сортировки, который имеет время выполнения O(n), а также сортирует на месте?

Answer 1

В некоторых случаях лучшим вариантом является O (n), но это, вероятно, потому, что коллекция элементов уже отсортирована.Вы смотрите на O (n log n) в среднем для некоторых из лучших.

С учетом сказанного, Wiki по алгоритмам сортировки довольно хорош.Есть таблица, в которой сравниваются популярные алгоритмы с указанием их сложности, требований к памяти (с указанием того, может ли алгоритм быть «на месте») и оставляют ли они элементы с одинаковыми значениями в их первоначальном порядке («стабильность»).

• http://en.wikipedia.org/wiki/Sorting_algorithm

Вот немного более интересный взгляд на производительность, предоставленный этой таблицей (из вышеупомянутой вики):

• http://en.wikipedia.org/wiki/File:SortingAlgoComp.png

Некоторые из них, очевидно, будет легче реализовать, чем другие, но я предполагаю, что те, которые стоит реализовать, уже были сделаны в библиотеке по вашему выбору.

Answer 2

Нет.

Для общей сортировки доказана нижняя граница O (n log n).

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

Answer 3

Radix Sort может сделать это:

http://en.wikipedia.org/wiki/Radix_sort#In-place_MSD_radix_sort_implementations

Answer 4

Сортировка спагетти - это O (n), хотя, возможно, не на месте. Кроме того, это только аналог.

Answer 5

Зависит от ввода и проблемы. Например, 1 ... n чисел могут быть отсортированы по O (n) по месту.