基排序运行时间

Question

如果我们有一些m>0，并且需要提供一种算法来排序O(mn)中在0到n^m-1范围内的n个整数。我的建议是：

Radix-Sort(A,t)  // t is the digit length
for i=0 to t
    do Insertion-Sort A on digit i

我的论点是，上面的操作将在O(mn)中运行，因为对于每一个数字，t插入排序将花费O(n)时间，因为每次运行的范围都很小。

这是正确的建议吗？以上的空间要求是什么？

谢谢。

Answer 1

空间要求是O(m + n)，因为您需要原始数字和m桶来放置n项。运行时是O(mn)，可以是>> n，这是基排序的问题。在所有情况下，它都是O(mn)，但问题是，如果m>n，则得到大于O(n^2)的值。根据编写方式的不同，在最坏的情况下，内存也可以是O(mn)，因为您创建了n个数字集的m个副本，以便对其排序。

Answer 2

使用计数排序更好，当对一个小范围的离散数进行排序时，它保证了搜索的线性度与数据大小及其范围(插入排序是一种与O(n^2)最坏情况复杂性相比较的排序，但是如果数据是按oposite方向排序的，那么这个小范围可能无法帮助您进行插入排序，因为每个元素都会被移动)。

使用计数排序时的空间复杂度为O(n+k)，其中n是数组的大小，k是数据的范围。您可以使用相同的数组对结果进行排序和返回，因为您正在对原始数据进行排序。