algorithm - 用 O(n) 中的值范围对数组进行排序

Question

有一个数组A[1, ..., n] ，它知道每个 1 <= l <= n然后 A[l] in {1,2,...,n^5} .

我怎样才能找到一个在 O(n) 中对它进行排序的算法？

Answer 1

想象在 Base-n 系统中表示 A[i] 中的值。然后每个数字变成一个五位数的 n 进制数，这意味着您可以使用 Radix Sort 的五个应用程序对整个数组进行排序。 ，“基数”为 n。

按如下方式计算数字 k 中每个“数字”x 的值:

d_x = (k/(n ^x)) % n

其中/表示整数除法。