我明白 32 位整数被分解为 8 位块。有人可以给我更多关于通行证如何工作的解释吗？一个简单的例子将帮助我更好地理解它。例如，我有 2147507648 和 2147507672。我将它们分解为 8 位块。128 0 093 216 是 2147507672 的细分，128 0 093 192 是 2147507648 的细分。
我了解 LSD 基数排序如何适用于基数 10。如果有人能告诉我在获得 8 位块后如何对这些 32 位整数进行排序，我将不胜感激。
非常感谢！
问问题
1000 次
2 回答
1
对一组数字进行基数排序背后的一般思想是将数字写入某个以 b 为底的数字，然后一次处理一个以 b 为底的数字。如果您对以 10 为基数的基数排序感到满意，那么调整算法以在其他基数中工作并不需要太多工作。
举个例子，假设我们想做一个以 2 为底（二进制）的基数排序。在这种情况下，我们将以 2 为底（二进制）写入数字。我们将有两个桶，而不是十个桶。我们不是一次看一个数字的位数，而是一次看一个数字的位。除此之外，该算法与base-10基本相同。
当您将数字分成 8 位组时，您可以考虑将数字以 256 为基数写入。为什么？好吧，类比推理，假设您采用以 10 为底的基数排序（您习惯使用的那种），而不是 10 个桶，而是 100 个桶。然后，不是一次处理一个数字，而是一次处理两个数字。这仍然可以正常工作（我希望你明白为什么！）并且实施起来并不难。此过程与使用 base-100 基数排序完全相同 - 通过将相邻的 base-10 数字组合在一起，您可以形成 base-100 数字。作为另一个示例，将数字分组为三个给出以 1000 为底的基数排序。所以现在让我们回到二进制。每个位都是以 2 为底的数字。一组两位可以被认为是一个基数为 4 的数字。一组四位可以被认为是一个基数为 16 的数字，
因此，要回答您的问题，从以 10 为基数的基数排序转换基数排序在每个 8 位块上的方法是考虑您正在做什么以作为基数 256 基数排序，然后相应地实现算法。
于 2015-08-26T21:06:52.083 回答
-1
在你跳进去之前Radix Sort，你是不是很熟悉了Counting Sort？
如果您理解Counting Sort了，那么您将很容易了解 Radix Sort 的工作原理并能够自己实现它。
您需要知道的另外几件事是跟踪数字的频率，然后计算累积频率。累积频率决定了最终排序数组中第 th 个元素的位置。
于 2013-10-16T06:39:16.787 回答