基数排序运行时间
如果我们有一些m>0并且需要提供一种算法来对0到n^m-1范围内的n个整数进行排序时间 O(mn)。我的建议是：
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) 时间，因为每次运行的范围很小。
这是正确的建议吗？上述空间要求应该是多少？
谢谢。
If we have some m>0 and need to provide an algorithm to sort n integers in the range 0 to n^m-1 in time O(mn). My suggestion is :
Radix-Sort(A,t) // t is the digit length
for i=0 to t
do Insertion-Sort A on digit i
My argument is that the above will run in O(mn) because for each digit t - Insertion sort will take O(n) time since the range for each run is small.
Is this the correct suggestion? What should be the space requirement of the above?
Thanks.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
在对小范围的离散数进行排序时，最好使用计数排序，因此它保证了搜索相对于数据大小及其范围的线性（插入排序是一种比较排序，最坏情况复杂度为 O(n^2)，但如果数据按相反的方向，小范围可能不会帮助您进行插入排序，因为每个元素都会被移动）。
使用计数排序时的空间复杂度将为
O(n+k)，其中n是数组的大小，k是数据的范围。您可以使用相同的数组来排序和返回结果，因为您正在对原始数据进行排序。Its better to use Counting sort, when sorting discrete numbers of a small range, hence it guarantees the linearity of the search in respect to the size of data and the their range (insertion sort is a comparison sort with
O(n^2)worst case complexity, but if the data were sorted in an oposite direction, the small range wont probably help you with insertion sort, because every element will be moved).The space complexity when using counting sort will be
O(n+k), where n is the size of the array and k is the range of the data. You can use the same array for sorting and returning the result, because you are sorting primitive data.空间要求是 O(m + n)，因为您需要原始数字和 m 个桶来放置 n 个项目。运行时间是O(mn)，可以是>> n 这是基数排序的问题。在所有情况下都是 O(mn) 但问题是如果 m > n 你得到的东西大于 O(n^2)。根据写入方式，在最坏的情况下，内存也可能是 O(mn)，因为您创建了要排序的 n 个数字集合的 m 个副本。
The space requirement is O(m + n) because you need the original numbers and m buckets to place the n items. The runtime is O(mn) which can be >> n which is the issue with radix sort. In all cases its O(mn) but the problem is that if m > n you get something larger than O(n^2). Depending on how it's written the memory can also be O(mn) in the worst case because you create m copies of the set of n numbers to sort on.