Алгоритм сортировки

Question

Вот тизер мозга, который был у меня в голове несколько дней.

У нас есть последовательность S из n элементов.Каждый элемент является целым числом в диапазоне [0, n ^ 2-1].Опишите простой метод сортировки S по времени O (n).

Возможно что-то очевидное, что я просто скучаю, но я был бы признателен за любую информацию.

Answer 1

Bucket Sort!

Bucket sort, или bin sort, - это алгоритм сортировки, который работает путем разделения массива на несколько сегментов.Затем каждый сегмент сортируется индивидуально, либо с использованием другого алгоритма сортировки, либо путем рекурсивного применения алгоритма сортировки сегмента.Это дистрибутивный тип, двоюродный брат радикального типа в наиболее значимом и значимом разряде.Сортировка ведра является обобщением сортировки голубя.Поскольку сортировка по сегментам не является сортировкой сравнения, нижняя граница Ω (n log n) неприменима.Оценки сложности вычислений включают количество сегментов.

Answer 2

Radix Sort! (это просто особый случай сортировки ведра).

Answer 3

Запишите в базе n и выполните сортировку сегментов, выполнив подсчет для каждого сегмента (области соответствуют цифрам в базе n).

O (n) время, O (n) пробел.

Answer 4

Быстрая сортировка - O (n log n), как стандартный «хороший алгоритм» для сортировки списка.Так что должен быть какой-то «трюк», чтобы перейти к O (n) времени.

Единственный реальный трюк с этими данными - это переход от 0 до n ^ 2-1 ... но яне могу придумать, как это можно использовать для сортировки за O (n) время ....

PS Звучит как домашнее задание, а не то, над чем вы "ломаете голову ради знания"

PPS Я потерпел неудачу, потому что не думал о сортировке ведра.