Сортировка за линейное время?[закрыто]

Question

Учитывая входной набор из n целых чисел в диапазоне [0..n ^ 3-1], предоставьте алгоритм сортировки по линейному времени.

Это обзор моего теста в четверг, и я понятия не имею, как подойти к этой проблеме.

Answer 1

Также взгляните на родственные сорта: сортировка по ячейкам или подсчет сортировки, а также сортировка по основанию как упоминал Пукку.

Answer 2

Взгляните на сортировка по основанию.

Answer 3

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

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

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

Answer 4

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

Answer 5

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

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

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

В противном случае используйте Сортировку по основанию:

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

Answer 6

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

Answer 7

Набор ограниченного диапазона чисел может быть представлен растровым изображением битов ДИАПАЗОНА.В данном случае растровое изображение размером 500 мб, так что для чего угодно, кроме огромных списков, вам лучше использовать сортировку по радиусу.Когда вы встретите число k, установите bitmap[k] = 1.Одиночный обход по списку, O(N).

Answer 8

подобный алгоритм возможен:

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

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