Массив длины N может содержать значения 1,2,3 ... N ^ 2.Можно ли отсортировать за O (n) время?

Question

Учитывая массив длины N. Он может содержать значения в диапазоне от 1 до N ^ 2 (N в квадрате), оба включительно, значения являются целыми. Можно ли отсортировать этот массив в O (N) времени? По возможности как?

Редактировать: это не домашняя работа.

Answer 1

Запишите каждое целое число в базе N, то есть каждый x может быть представлен как (x1, x2) с x = 1 + x1 + x2 * N.Теперь вы можете отсортировать его дважды с помощью счетчика сортировки, один раз по x1 и один раз по x2, что приведет к сортировке массива.

Answer 2

Да, вы можете, используя radix sort с N корзинами и двумя проходами.По сути, вы рассматриваете числа как имеющие 2 цифры в базе N .

Answer 3

Можно отсортировать любой массив целых чисел с четко определенным максимальным значением за O(n) время, используя radix sort . Это, вероятно, относится к любому списку целых чисел, с которыми вы сталкиваетесь. Например, если вы сортируете список произвольных целых чисел, это не будет правдой. Но все целочисленные типы C имеют четко определенные фиксированные диапазоны.