添加到集合然后对其进行排序还是添加到已排序的集合更快？

sorting collections java

2022-08-31 12:08:23

如果我有这样的话：Map

HashMap<Integer, ComparableObject> map;

并且我想获得使用自然排序排序的值的集合，哪种方法最快？

（一）

创建可排序集合的实例，例如，添加值，然后对其进行排序：ArrayList

List<ComparableObject> sortedCollection = new ArrayList<ComparableObject>(map.values());
Collections.sort(sortedCollection);

创建一个有序集合的实例，如，然后添加值：TreeSet

Set<ComparableObject> sortedCollection = new TreeSet<ComparableObject>(map.values());

请注意，生成的集合永远不会被修改，因此排序只需要进行一次。

答案 1

TreeSet 具有方法的时间复杂度保证。排序需要操作，但只执行操作。log(n)add()/remove()/contains()ArrayListn*log(n)add()/get()1

因此，如果您主要检索，并且不经常排序，则是更好的选择。如果您经常排序但不检索那么多，那将是一个更好的选择。ArrayListTreeSet

答案 2

从理论上讲，最后的排序应该更快。在整个过程中维护排序状态可能需要额外的 CPU 时间。

从 CS 的角度来看，这两个操作都是 NlogN，但 1 排序应该具有较低的常量。