对任意长度的二进制字符串进行基数排序

我搜索了一下，看到关于二进制字符串基数排序的大量讨论，但它们都有相同的长度，如何使用任意长度的aobut二进制字符串？对任意长度的二进制字符串进行基数排序

说我有{“001”，“10101”，“011010”，“10”，“111”}，我如何对它们进行基数排序？谢谢！

来源

2010-01-31 ohana

查找最大长度并将它们全部填充到该长度。如果长度最长的字符串的长度有一些上限，应该仍然表现良好。

来源

2010-01-31 03:14:39

原则上相同的事情，但...将字符串转换为整数？ – Steve314 2010-01-31 03:17:41

您可以将它们全部填充为相同的长度，但是没有真正的理由运行排序算法来确定二进制中的长度5数大于长度2。通过按长度对数字进行分组并在每个组内运行基数排序，您可能会获得更好的性能。当然，这取决于你如何对他们进行分组，然后依据你如何分类你的组。

如何做到这一点的一个例子是运行所有的项目一次，并将它们全部扔到一个哈希表（长度 - >该数字的长度）。这需要线性时间，然后让我们说nlogn时间来按顺序访问它们。基数排序以O（nk）时间运行，其中n是项目的数量，k是它们的平均长度。如果你有一个很大的k，那么O（nk）和O（nlogn）之间的差异是可以接受的。

来源

2010-01-31 03:27:58 karenc

不错，但... 不会重新分组它们需要预排序操作来将所有字符串排序到合适的组中吗？ – FrustratedWithFormsDesigner 2010-01-31 03:31:03

是的，对于小k来说可能不值得。基数排序是一种“线性”时间排序算法，如果您假设k是一个常数或至少很小。但是对于大K而言，预分类将是值得的。预先排序的方式可能比我上面提到的要好，但这是想到的第一个合理的方式。 – karenc 2010-01-31 03:35:42

-1

如果创建大量新的字符串实例会留下令人厌恶的味道，请自行编写比较。

比较什么字符串的长度将没有前导0（即找到firstIndexOf("1")）;较长的字符串较大。
如果二者的长度相同，则继续逐字比较它们，直到找到两个不同的字符 - 带有“1”的字符串较大。

来源

2010-01-31 03:36:18

不知道为什么downvote：用一个新的字符串替换每个字符串（按照最高票数的答案）将使算法所需的内存增加一倍以上，这在很多情况下很可能是一个问题。 – 2011-01-30 02:06:48

对任意长度的二进制字符串进行基数排序

回答

相关问题