正如书中给出的那样，基数排序通常是从 LSB 到 MSB 完成的。但是我认为通过使用 MSB 到 LSB，我们可以将输入元素划分为更小的分区。现在我必须构建一个示例来说明 MSB 优先基数排序可能比 LSB 优先基数排序渐进地差。这是我的分配问题。
问问题
1829 次
2 回答
1
设排序范围为[1,n2]，即我们需要在[1,n]范围内两次应用桶排序。如果我们使用 MSB 优先排序，那么时间界限是 ∑(i=1 到 n) O(ni +n)，其中 ni 是桶中（MSB 的）元素的数量。LSB 的范围是 [1, n]。同样对 [1, n] 范围内的 m 个数字进行排序需要时间 O(m + n)。∑(i=1 to n) O(ni +n) = n + ∑(i=1 to n) n 的值可以是Ω(n2)。
于 2012-09-08T12:49:09.103 回答
0
基数排序并不像第一次出现所暗示的那样有限。它现在是许多 GPGPU 排序的核心（哇！双音排序又回到了壁橱里）。我写了使基数排序适用于许多数据集的基本方法，其中键可以由 memcmp(3) 在这个关于基数排序的谷歌文档中排序---将图表复制到 stackoverflow 文本框中是超出我的:-)最大的“障碍”是不遵循快速排序的“分而治之”方法，因为它重复了 MSB 基数排序的昂贵启动成本。“分治法”的基数排序等价物是将输入集减少为已排序和未排序范围的列表，并在每次传递中一起处理所有剩余的未排序范围。. 高温高压
于 2013-08-08T02:37:42.490 回答