上周我偶然发现了这篇论文,作者在第二页提到:
请注意,这会产生整数边权重的线性运行时间.
第三页上的内容相同:
这产生整数边缘权重的线性运行时间和基于比较的排序的O(m log n).
在第8页:
特别是,使用快速整数排序可能会显着加速GPA.
这是否意味着在特殊情况下存在整数值的O(n)排序算法？或者这是图论的专长？
PS:
可能参考文献[3]可能会有所帮助,因为在第一页上他们说:
[...]图表类已经实现了进一步的改进,例如整数边权重[3],[...]
但是我无法访问任何科学期刊.
我的文件中有一百万行。从每一行创建一个对象并将其添加到集合中。compareTo()必须使用类的自定义方法对集合进行排序。
目前我ArrayList按照阅读顺序将对象添加到 an 中，然后执行Collections.sort().
制作 TreeSet 会更快吗？