我有一个迭代器，它给我 n 个元素。目前，我将它们一一复制到 ArrayList 中，然后在该列表上调用 Collections.Sort() 以获得排序的 ArrayList。这需要 nlog(n)+n 次操作。有没有更快的方法来做到这一点，即我可以在一定程度上使用插入操作吗？
迭代器不进行任何排序，元素几乎随机出现。
最佳答案
如果你只有那个迭代器，我看不到更快的解决方案。请注意，nlogn+n 也是 O(nlogn)。
如果你想“边插入边排序”，你需要在每次插入时进行二分查找，这也是O(nlogn)。我不认为它会比你所拥有的快得多。
TreeSet 可以让你免于二分查找的实现，但基本上是相同的逻辑。
关于java - 插入时排序或复制并排序，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/24136930/