3

我四处搜索，看到很多关于二进制字符串的基数排序的讨论，但它们都具有相同的长度，如何使用任意长度的二进制字符串？

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

4

3 回答 3

2

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

于 2010-01-31T03:14:39.747 回答
2

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

您可以如何执行此操作的一个示例是遍历所有项目一次并将它们全部放入哈希表（长度->该长度的数字）。这需要线性时间，然后让我们说 nlogn 时间按顺序访问它们。基数排序在 O(nk) 时间内运行，其中 n 是项目数，k 是它们的平均长度。如果你有一个很大的 k，那么 O(nk) 和 O(nlogn) 之间的差异是可以接受的。

于 2010-01-31T03:27:58.900 回答
-1

如果创建大量新字符串实例让人讨厌，请自己编写比较。

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

于 2010-01-31T03:36:18.667 回答