我有一个迭代器，它给我n个元素。目前，我将它们一个接一个地复制到ArrayList中，然后在该列表上调用Collections.Sort()以获得排序的ArrayList。这需要nlog(n)+n次操作。是否有一种更快的方法来做到这一点，即我是否已经在一定程度上使用了插入操作?
迭代器不进行任何排序，元素几乎是随机出现的。
如果你只有那个迭代器，我看不到更快的解决方案。注意nlogn+n也是O(nlogn)。
如果你想"在插入时排序"，你需要在每次插入时进行二进制搜索，它也将是O(nlogn)。我不认为它会比你现有的快多少。
TreeSet可以将您从二进制搜索实现中拯救出来，但基本上它是相同的逻辑。
由于迭代器既不是集合也不是容器，因此不可能在迭代器中直接排序，正如您已经注意到的那样。您使用的方法似乎是这种情况下的最佳解决方案。
如果你的元素是唯一的，你可以把它们放到TreeSet中，然后把它们从TreeSet复制到ArrayList中。这可能并不比你已经在做的事情快。
除此之外，你不太可能在现有的基础上进一步优化。编写自己的插入排序几乎肯定比使用高度优化的Java排序例程要慢。
你可以考虑看看Java 8中新的Java Streams API。这样就可以将迭代器作为流打开，对其排序，然后将其排序到最终集合。
http://docs.oracle.com/javase/8/docs/api/java/util/stream/package-summary.html如果数组中有一个对象而不是原始数据类型(如int、double)，则必须考虑对象复制的成本。在这种情况下，对数组索引排序可能是更好的方法。只有在需要同时处理排序和插入时，才使用搜索数据结构map/set。