我在网上搜索了一下二进制字符串的基数排序,但是它们都是相同长度的,如果长度任意怎么办? 比如说我有{"001", "10101", "011010", "10", "111"},我应该如何对它们进行基数排序?谢谢!
你可以将所有数字填充为相同的长度,但没有真正的理由运行排序算法来确定二进制中长度为5的数字是否比长度为2的数字大。你可能会通过按长度分组并在每个组内运行基数排序来获得更好的性能。当然,这取决于你如何分组,以及如何对你的组进行排序。一个例子是,你可以遍历所有项目一次,将它们全部放入哈希表(长度-->该长度数字的数量)。这需要线性时间,然后假设访问它们需要nlogn的时间才能按顺序访问。基数排序的运行时间为O(nk),其中n是项目数量,k是它们的平均长度。如果k很大,则O(nk)与O(nlogn)之间的差异将是可以接受的。
如果创建大量新字符串实例让人感觉不爽,那么可以自己编写比较方法。比较没有前导零的字符串长度(即查找firstIndexOf("1")); 更长的字符串更大。 如果两个字符串长度相同,就按字符逐一比较,直到找到两个不同的字符 - 带有“1”的字符串更大。