Сортировка n чисел между [0, n ^ 2 - 1] в O (n)?

Учитывая n числа в диапазоне [0,n^2 -1], как мы можем отсортировать их в O (n) времени выполнения?

У меня такое ощущение, что решение включает radix sort, но я все еще ничего не вижу.

Ответы

Фактическое время будет зависеть от распределения данных, которые у вас есть, но я бы сделал следующее:

Сделайте n ковшей.
Пройдите через каждое число и поместите элемент со значением я в bucket sqrt (i).
Пройдите через каждое ведро и выполните сортировку по основанию для каждого элемента в ковше.

Я думаю, тебе не повезло. Radix sort - это O (k * n), где k - количество цифр. В вашем случае k = log (n ^ 2), что приводит к O (n * log (n)).