logo标签列表

在任意长度的二进制字符串上使用基数排序

stringbinarysortingradix
3

我在网上搜索了一下二进制字符串的基数排序，但是它们都是相同长度的，如果长度任意怎么办？

比如说我有{"001", "10101", "011010", "10", "111"}，我应该如何对它们进行基数排序？谢谢！

3个回答
2
找到最大的长度，并将它们全部填充到该长度。如果最长字符串的长度有一个上限，那么仍然可以保持良好的性能。
3
原则上是同样的事情，但是...把字符串转换为整数？ - user180247
2
你可以将所有数字填充为相同的长度，但没有真正的理由运行排序算法来确定二进制中长度为5的数字是否比长度为2的数字大。你可能会通过按长度分组并在每个组内运行基数排序来获得更好的性能。当然，这取决于你如何分组，以及如何对你的组进行排序。
一个例子是，你可以遍历所有项目一次，将它们全部放入哈希表（长度-->该长度数字的数量）。这需要线性时间，然后假设访问它们需要nlogn的时间才能按顺序访问。基数排序的运行时间为O(nk)，其中n是项目数量，k是它们的平均长度。如果k很大，则O(nk)与O(nlogn)之间的差异将是可以接受的。
还不错，但是... 重新分组需要一个预排序操作来将所有字符串按正确的组进行排序吗？ - FrustratedWithFormsDesigner
是的，对于一个小的k值可能不值得。 基数排序是一种“线性”时间排序算法，如果您假设k是一个常数或至少很小的话。但对于大的k值，预排序将是值得的。而且可能有比我上面建议的更好的预排序方法，但那是我想到的第一个合理的方法。 - karenc
-1
如果创建大量新字符串实例让人感觉不爽，那么可以自己编写比较方法。
比较没有前导零的字符串长度（即查找firstIndexOf("1")）; 更长的字符串更大。
如果两个字符串长度相同，就按字符逐一比较，直到找到两个不同的字符 - 带有“1”的字符串更大。
不确定为什么会被踩：按照得票最高的答案，用新字符串替换每个字符串将使算法所需的内存超过两倍，这在许多情况下可能会成为一个问题。 - BlueRaja - Danny Pflughoeft
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接