另一点是插入操作的时间复杂度。 对于列表插入，期望复杂度为O(1)。 但是，排序的列表并不能保证这一点。

最重要的一点是，列表对它们的元素没有任何假设。 例如，您可以列出不实现等于或比较的东西。

https://github.com/geniot/indexed-tree-map

考虑使用索引树映射。它是一个增强的JDK的TreeSet，它提供了通过索引访问元素的功能，并且无需迭代或隐藏的底层列表来备份树，就可以找到元素的索引。该算法基于每次有变化时更新已更改节点的权重。

另一点是插入操作的时间复杂度。 对于列表插入，期望复杂度为O(1)。 但是，排序的列表并不能保证这一点。

最重要的一点是，列表对它们的元素没有任何假设。 例如，您可以列出不实现等于或比较的东西。

列表迭代器首先保证以列表的内部顺序获取列表的元素。插入顺序)。更具体地说，它是在您插入元素的顺序或您如何操作列表。排序可以看作是对数据结构的操作，有几种方法可以对列表进行排序。

我将按照我个人认为的有用性来排序:

1. 可以考虑使用Set或Bag集合

注意:我把这个选项放在顶部，因为这是你通常想要做的。

排序集在插入时自动对集合进行排序，这意味着它在向集合中添加元素时进行排序。这也意味着您不需要手动排序。

此外，如果您确定不需要担心(或没有)重复元素，则可以使用TreeSet<T>代替。它实现了SortedSet和NavigableSet接口，并像你可能期望的那样从列表中工作:

TreeSet<String> set = new TreeSet<String>();
set.add("lol");
set.add("cat");
// automatically sorts natural order when adding

for (String s : set) {
    System.out.println(s);
}
// Prints out "cat" and "lol"

如果不想要自然排序，可以使用接受Comparator<T>的构造函数参数。

或者，您可以使用Multisets(也称为Bags)，这是一个允许重复元素的集合，而不是它们的第三方实现。Guava库中最值得注意的是TreeMultiset，它的工作原理与TreeSet非常相似。

2. 使用Collections.sort()对列表进行排序

如上所述，list的排序是对数据结构的操作。因此，当你需要“一个真相来源”以各种方式排序时，手动排序是可行的。

您可以使用java.util.Collections.sort()方法对列表进行排序。下面是一个代码示例:

List<String> strings = new ArrayList<String>()
strings.add("lol");
strings.add("cat");

Collections.sort(strings);
for (String s : strings) {
    System.out.println(s);
}
// Prints out "cat" and "lol"

使用比较器

一个明显的好处是可以在sort方法中使用Comparator。Java还为Comparator提供了一些实现，例如Collator，它对于locale敏感的字符串排序非常有用。这里有一个例子:

Collator usCollator = Collator.getInstance(Locale.US);
usCollator.setStrength(Collator.PRIMARY); // ignores casing

Collections.sort(strings, usCollator);

并发环境中的排序

但是请注意，在并发环境中使用sort方法并不友好，因为集合实例将被操作，您应该考虑使用不可变的集合。这是Guava在ordered类中提供的东西，是一个简单的一行程序:

List<string> sorted = Ordering.natural().sortedCopy(strings);

3.用java.util.PriorityQueue包装列表

虽然在Java中没有排序的列表，但是有一个排序的队列，它可能同样适合你。它是java.util.PriorityQueue类。

Nico Haase在评论中链接了一个相关的问题，也回答了这个问题。

在排序集合中，您很可能不希望操作内部数据结构，这就是为什么PriorityQueue没有实现List接口(因为这会让您直接访问其元素)。

关于PriorityQueue迭代器的警告

PriorityQueue类实现了Iterable<E>和Collection<E>接口，因此它可以像往常一样迭代。但是，迭代器不能保证按排序顺序返回元素。相反(正如Alderath在评论中指出的那样)，您需要轮询()队列直到空为止。

注意，你可以通过接受任何集合的构造函数将列表转换为优先级队列:

List<String> strings = new ArrayList<String>()
strings.add("lol");
strings.add("cat");

PriorityQueue<String> sortedStrings = new PriorityQueue(strings);
while(!sortedStrings.isEmpty()) {
    System.out.println(sortedStrings.poll());
}
// Prints out "cat" and "lol"

4. 编写自己的SortedList类

注意:您不必这样做。

您可以编写自己的List类，在每次添加新元素时进行排序。根据你的实现，这可能会使计算量相当大，而且毫无意义，除非你想把它作为练习，因为两个主要原因:

它打破了List<E>接口的契约，因为add方法应该确保元素驻留在用户指定的索引中。 为什么要重新发明轮子?你应该使用树集或多集，而不是在上面的第一点指出。

但是，如果你想把它作为练习，这里有一个代码示例来开始，它使用了AbstractList抽象类:

public class SortedList<E> extends AbstractList<E> {

    private ArrayList<E> internalList = new ArrayList<E>();

    // Note that add(E e) in AbstractList is calling this one
    @Override 
    public void add(int position, E e) {
        internalList.add(e);
        Collections.sort(internalList, null);
    }

    @Override
    public E get(int i) {
        return internalList.get(i);
    }

    @Override
    public int size() {
        return internalList.size();
    }

}

注意，如果您还没有覆盖所需的方法，那么AbstractList中的默认实现将抛出unsupportedoperationexception。

因为所有列表都已经按照条目的添加顺序(FIFO顺序)“排序”了，所以可以使用java.util.Collections.sort()使用另一种顺序“使用”它们，包括元素的自然顺序。

编辑:

列表作为数据结构的基础是有趣的是插入项的顺序。

集合没有这个信息。

如果您想通过添加时间来排序，请使用List。如果您想按其他标准排序，请使用SortedSet。

Set和Map是非线性数据结构。列表是线性数据结构。

---

树数据结构SortedSet和SortedMap接口使用常用的红黑树实现算法分别实现TreeSet和TreeMap。因此，它确保没有重复的项(或Map情况下的键)。

List已经维护了有序的集合和基于索引的数据结构，树不是基于索引的数据结构。 树根据定义不能包含重复项。 在List中，我们可以有副本，所以没有TreeList(即。没有SortedList)。 List按插入顺序维护元素。因此，如果我们想对列表进行排序，就必须使用java.util.Collections.sort()。它根据元素的自然顺序，将指定的列表按升序排序。