使用自定义比较器时,使用TreeSet或ArrayList是否更好？

Question

我已经实现了一个图表.我想根据它们的度数对给定的顶点子集进行排序.因此,我写了一个名为的自定义比较器DegreeComparator.

private class DegreeComparator implements Comparator<Integer>
{
    @Override
    public int compare(Integer arg0, Integer arg1) 
    {
        if(adj[arg1].size() == adj[arg0].size()) return arg1 - arg0;
        else return adj[arg1].size() - adj[arg0].size());
    }

}

那么,下面哪一个更有效率？

运用 TreeSet

public Collection<Integer> sort(Collection<Integer> unsorted)
{
    Set<Integer> sorted = new TreeSet<Integer>(new DegreeComparator());
    sorted.addAll(unsorted);
    return sorted;
}

运用 ArrayList

Collections.sort(unsorted, new DegreeComparator());

请注意,第二种方法不是函数,而是单行代码.

直观地说,我宁愿选择第二个.但我不确定它是否更有效率.

Answer 1

Java API包含许多Collection和Map实现,因此可能会弄清楚要使用哪一个.这是一个快速的流程图,可能有助于从最常见的实现中进行选择

Answer 2

TreeSet是一个Set.它删除重复项(具有相同程度的元素).所以两者都不相同.

无论如何,如果您想要的自然是排序列表,那么对列表进行排序.无论集合是否具有重复,这都将起作用,即使它具有与填充TreeSet相同的复杂度(O(n*log(n)),它也可能更快(因为它只需要移动数组中的元素,而不是必须创建大量的树节点).