Сортировка по линейному времени?

Ответ 1

Также взгляните на связанные сорта: сортировка свиньи или подсчет sort, а также сортировка radix, как упоминалось в Pukku.

Ответ 2

Посмотрите сортировку radix.

Ответ 3

Когда люди говорят "алгоритм сортировки", они часто ссылаются на "алгоритм сортировки сравнения", который является любым алгоритмом, который зависит только от возможности спросить "эта вещь больше или меньше". Поэтому, если вы ограничены вопросом об этом вопросе о данных, вы никогда не получите больше, чем n * log (n) (это результат выполнения log (n) поиска n факториальных возможных порядков набора данных),

Если вы можете избежать ограничений "сортировки сортировки" и задать более сложный вопрос о части данных, например "то, что является базовым основанием 10 этих данных", тогда вы можете найти любое количество линейных времен алгоритмов сортировки, они просто занимают больше памяти.

Это временное пространство. Сортировка сравнения занимает мало или вообще не работает и работает в N * log (n) времени. (например) выполняется в O (n) времени AND O (log (radix)).

Ответ 4

Это действительно просто, если n = 2 и числа уникальны:

• Построить массив бит (2 ^ 31-1 бит = > ~ 256 МБ). Инициализируйте их до нуля.
• Прочитайте ввод, для каждого значения, которое вы видите, установите соответствующий бит в массиве равным 1.
• Сканирование массива для каждого установленного бита выводит соответствующее значение.

Сложность = > O (2n)

В противном случае используйте Radix Sort:

Сложность = > O (kn) (надеюсь)

Ответ 5

wikipedia показывает довольно много разных алгоритмов сортировки и их сложности. вы можете проверить их

Ответ 6

A Набор ограниченного диапазона чисел может быть представлен битмапом бит RANGE. В этом случае растровое изображение 500 МБ, поэтому для чего угодно, кроме огромных списков, вам будет лучше с Radix Sort. Когда вы встретите число k, установите растровое изображение [k] = 1. Одиночный обход по списку, O (N).

Ответ 7

Думайте цифры как трехзначные числа, где каждая цифра колеблется от 0 до n-1. Сортируйте эти числа с помощью сортировки radix. Для каждой цифры есть вызов для подсчета сортировки, который принимает время Theta (n + n), так что общее время работы соответствует Theta (n).

Ответ 8

algo возможен:

M;// unsorted array
lngth; //number items of M
for(int i=0; i < lngth; i++)sorted[M[i]];

Это единственный возможный алгоритм для линейной сложности, но он имеет сложность O (k * N) by ram (элементы массива N - число, k - элемент len)