问题标签 [radix]

我已经给这个算法时间，但仍然无法弄清楚我在哪里做错了什么。任何人都可以帮助我解决“基数排序”的逻辑，如果我使用以下代码做得正确，那么请帮助我弄清楚为什么我会在 line:arr[sortedIndex] = tempArray[j][k]; 处得到 ArrayIndexOutOfBoundsException；

我正在开发一个程序来使用基数排序对数字列表进行排序，但我一直陷入我认为是无限循环的困境。我认为它要么是我的主要排序功能，要么是我的计数功能。关于我做错了什么的任何想法？

我非常接近让这个程序工作，但我试图让这个程序使用基数排序按字母顺序排列一组字符串，并且在弄清楚如何

第一次迭代效果很好，并按第一个字符对所有字符串进行排序。但是，第二次迭代将所有这些都抛到了窗外，并按第二个字符对它们进行排序。如何解决此问题以使其正常工作？

我有一个运行 C 代码的嵌入式系统，它的工作非常简单；它通过串行连接读取字符，将接收到的字符解释为十六进制数字，并根据接收到的内容，继续执行其他操作。但是，有一种非常特殊的情况，接收到的字符是十进制而不是十六进制。由于这种情况非常罕见（一种错误情况的错误情况），我不希望修改实际的字符接收来决定是否将接收到的值解释为 dec 或 hex，而是添加一个快速算法到我将数字更改为十进制的情况处理。

你会说什么是最快的（如在最有效的处理器方面）这样做的方式？由于该软件在小型 MCU 上运行，因此任何 C 库函数都不是一个选项，因为我不希望添加更多不必要的#include，因此我正在寻找纯数学算法。

为了清楚起见，我不是在问最快的方法来进行基本的十六进制到十进制转换，如 0x45 -> dec 69，但我想做的是转换例如。0x120 转化为十进制 120。

提前致谢！

编辑：对不起，我会尝试更详细地解释。实际代码太长了，我认为没有必要在这里粘贴。所以这就是发生的事情：

首先，我从串行线上读取接收到的数字，比如说“25”。然后我把它变成十六进制数，所以我有一个带有读取值的变量，比如说 X = 0x25。这已经很好了，我不想对此进行修改。在这种非常特殊的情况下，我现在想做的只是改变变量的解释，而不是 X == 0x25，X==25。十六进制的 0x25 变成十进制的 25。这种变化必须有某种数学公式，而不需要任何特定于处理器的指令或库函数？

我很难理解基数排序。我在实现代码以使用 2 或 10 的基数时没有问题。但是，我有一个需要命令行参数来指定基数的分配。基数可以是 2 - 100,000 之间的任何值。我花了大约 10 个小时试图理解这个问题。我不要求直接回答，因为这是家庭作业。但是，如果有人可以对此有所了解，请这样做。

有几件事我不明白。基数为 100,000 有什么意义？那怎么行。我知道字母表中的每个字母或每个数字 1-9 都有一个基数。我似乎无法理解这个概念。

如果我不够具体，我很抱歉。

我已经阅读了关于这个主题的几个来源。但是，我很难弄清楚这些公式的确切含义。当 b = n 时，基数排序似乎是线性的。这是否意味着，我应该将基数设置为数组的长度？

如果我有一个 1 亿个整数的数组，范围从 0 到 10 亿，我应该选择基数 1 亿？

如果这不正确，请尝试为我简化它。我能找到的大多数基数排序示例只有以 10 为底或以 2 为底，因此它们对于分别大于 10 或 2 的数组来说很慢，或者我就是不明白。

谢谢你的帮助。

Pierre Terdiman 在他的文章“Radix Sort Revisited”中告诉我们：

例如，您需要 4 次通过才能对标准 32 位整数进行排序，因为在十六进制中，基数是一个字节。

但是 0xAB 有两个基数，即 A 和 B，都是 4 位宽。

那么，十六进制的基数是什么？因为看不懂文章。

我需要为 IPv6 创建白名单/阻止名单。

在 IPv6 中，有哪些内存选项可用于在每个主机或每个网络的基础上维护信息？

我目前HashTable<UInt32>为 IPv4 使用 a，但从未真正掌握子网跟踪、CIDR 等。IPv6 有许多不同的方式来表示 IP 范围，这使我将 IP 组合在一起并解释它们的工作变得复杂。

话虽如此..拥有这样一个阻止列表/白名单的最有效方式（搜索速度或内存紧凑性）是什么？

TL;DR 问题

• 如何查找 aUInt128是否在列表/btree/哈希表中？哪种数据结构适合这个？

• 如何找到彼此“接近”的 IP。这通常称为 CIDR，但我们也可以将其表示为 BigInt 的值比较。

我刚刚想到的一种方法是加密累加器的工作原理。也许有一种方法可以利用累加器的“成员资格”能力来确定一个数字是否是集合的成员

引号中的文字为我的程序提供了一些背景知识，以防需要理解我的问题，如果您不想阅读它，您可能能够完全理解末尾未引用的内容。

我正在研究 C++ 中排序的常见项目，我目前正在做基数排序。我把它作为一个函数，接受一个字符串向量、一个包含最大位数的整数和一个带有数字基数/基数的整数：(numbers, maxDigits, radix)

由于该程序接受不同基数的数字并作为字符串，因此我使用 stoi 将它们转换为以 10 为基数的整数，以使该过程更易于概括。以下是该算法的快速摘要：

• 创建 10 个队列来保存值 0 到 9
• 遍历每个数字（maxDigit 次）
  
  • 遍历向量中的每个数字（这里它转换为以 10 为底）
  • 根据它正在查看的当前数字将它们放入队列
  • 将数字从队列中从头到尾拉回向量中

至于我试图解决的问题，我想在将 maxDigit 值（用户输入的任何基数）转换为基数 10 后将其更改为 maxDigit 值。换句话说，假设用户使用了代码

对最大位数为 8 且基数为 2 的数字向量进行排序。由于我将数字的基数转换为 10，因此我正在尝试找到一种算法来更改 maxDigits，如果这有意义的话。

我已经尝试过这么多的思考，试图通过反复试验找出一种简单的方法。如果我能在正确的方向上获得一些提示或帮助，那将是一个很大的帮助。

我在编写算法来查找特里树的高度时遇到了麻烦。我不知道如何开始或如何做。抱歉，如果这是一个“菜鸟”问题，但我对尝试很陌生，这是我作业中唯一缺少的部分。

无论如何，这里是特里树的结构：

所以基本上，如果'a'是一个孩子，那么在chidren[0]中会有一个Trie，如果'b'不是孩子，children[1]将为NULL。如您所见，字符由链接索引隐式定义，如果过去节点的字符在当前节点之前形成一个单词，则“Boolean IsItAWord”将为真。

你们能给我一点启示吗？我唯一知道的是，高度可以由最长单词的长度 + 1 来定义。但我不知道该怎么做。我真的只是想要一个解决方案，所以任何找到这个 trie 高度的方法都将不胜感激。

谢谢你。