Нижняя граница для сортировки n-значений на основе сравнения в диапазоне от 1 до k

Можем ли мы улучшить время O (n lg n) для алгоритма на основе сравнения, когда все значения находятся в диапазоне от 1 до k, где k < п.

Сортировка сортировки и сортировка оснований не являются алгоритмами на основе сравнения и запрещены. По анализу дерева решений кажется, что существует k ^ n возможных перестановок. Есть 2 ^ h листьев, поэтому должно быть возможно решить проблему в O (n lg k) time с помощью алгоритма сортировки на основе сравнения.

Пожалуйста, не давайте алгоритм сортировки, основанный на сравнении, для решения этой проблемы, вся сортировка должна основываться на сравнении двух элементов. Спасибо!

Ответ 1

Это можно легко сделать в указанной вами связи. Создайте двоичное дерево из k листьев и включите значение счета для каждого листа. Обработка каждого элемента (добавление его или наложение счетчика) будет O (lg k), если вы используете подходящий алгоритм балансировки, поэтому все они будут O (n lg k). Подтверждением списка будет O (n).

Ответ 2

Хорошо, если вы настаиваете на необходимости сравнения.

У вас есть элементы k. Итак, сохраните древовидную структуру, которая будет содержать все элементы.

Перейдите по списку элементов, каждый раз добавляя элемент к дереву. Если элемент уже находится в дереве, просто увеличивайте счетчик в node. (или если вы хотите, чтобы фактические элементы вы могли сохранить список в каждом node)

Дерево будет содержать не более k.

в конце, перейдите дерево по-некорректному и добавьте элементы в правильном порядке (при добавлении количества, которое находится в счетчике node).

Сложность: O (nlogk)

Ответ 3

Да, вы можете использовать массив размером k. (Без сравнений)

Каждая ячейка я будет содержать список.
перейдите к исходному массиву, поместите каждый элемент в список правой ячейки.

Перейдите по второму массиву и вытащите их, верните их в правильном порядке.

О (п)