为什么在Java中没有SortedList？
在Java中有SortedSet和SortedMap接口。 两者都属于Java的标准集合框架，并提供了访问元素的排序方式。
但是，据我了解，Java中没有SortedList 。 您可以使用java.util.Collections.sort()对列表进行排序。
任何想法，为什么它是这样设计的？
列表迭代器首先保证列表的元素以列表的内部顺序（即插入顺序 ）。 更具体地说，它是按照你插入元素的顺序或者你如何操纵列表。 排序可以看作是对数据结构的一种操纵，并且有几种排序列表的方法。
我将按照我个人的看法，按照有用的顺序排列：
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 ，它对于语言环境敏感的排序字符串很有用。 这里是一个例子：
Collator usCollator = Collator.getInstance(Locale.US); usCollator.setStrength(Collator.PRIMARY); // ignores casing Collections.sort(strings, usCollator);
排序在并发环境中
请注意，尽管在并发环境中使用sort方法不友好，因为集合实例将被操纵，您应该考虑使用不可变集合。 这是Guava在Ordering课程中提供的，是一个简单的单线程：
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在评论中指出的），你需要poll()队列直到空。
请注意，您可以通过构造函数将列表转换为优先级队列：
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方法应该确保元素将驻留在用户指定的索引中。 - 为什么重新发明轮子？ 您应该使用TreeSet或Multisets，而不是像上面第一点中指出的那样。
但是，如果您想将其作为练习来做，那么您可以使用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 。
因为List的概念与自动排序集合的概念是不相容的。 List的要点是在调用list.add(7, elem) ，对list.get(7)的调用将返回elem 。 使用自动排序的列表，该元素可以在任意位置结束。
由于所有列表已经按照项目添加的顺序（FIFO顺序）“排序”，因此可以使用java.util.Collections.sort()以其他排序（包括元素的自然顺序）“排序”它们。
编辑：
作为数据结构的列表基于有趣的是插入项目的顺序。
集合没有这些信息。
如果您想按添加时间排序，请使用List 。 如果您想按其他条件排序，请使用SortedSet 。
对于任何新来者，截至2015年4月，Android现在在支持库中都有一个SortedList类，专门用于RecyclerView 。 这是关于它的博客文章 。
Set和Map是非线性数据结构。 列表是线性数据结构。
树型数据结构SortedSet和SortedMap接口分别使用红黑树实现算法实现TreeSet和TreeMap 。 所以它确保没有重复项目（或Map密钥）。
- 树根据定义不能包含重复。
- 在
List我们可以有重复的，所以没有TreeList。
所以，如果我们想排序列表，我们必须使用java.util.Collections.sort() 。
另一点是插入操作的时间复杂度。 对于列表插入，需要复杂度为O（1）。 但是这不能通过排序列表来保证。
而且最重要的一点是，列表中没有任何关于它们的元素。 例如，您可以列出不执行equals或compare的事情。
虽然花了一些时间，Java 8确实有一个排序列表。 http://docs.oracle.com/javase/8/javafx/api/javafx/collections/transformation/SortedList.html
正如您在javadocs中看到的那样，它是JavaFX集合的一部分，旨在提供ObservableList上的排序视图。
像这样想： List接口有像add(int index, E element) ， set(int index, E element) 。 合同是，一旦你在位置X添加了一个元素，你将会在那里找到它，除非你在它之前添加或删除元素。
如果任何列表实现将存储的元素以某种顺序而不是基于索引，上面的列表方法将是没有意义的。
List API中的第一行表示它是一个有序集合（也称为序列）。 如果对列表排序，则无法维护顺序，因此Java中没有TreeList。
由于API说Java列表从序列中获得了启发，并且看到了序列属性http://en.wikipedia.org/wiki/Sequence_(mathematics ）
这并不意味着你不能对列表进行排序，但是Java对他的定义是严格的，并且默认情况下不提供排序的列表版本。
考虑使用索引树映射 。 它是一个增强的JDK的TreeSet，它提供了通过索引来访问元素，并找到没有迭代的元素索引或隐藏的备份树的基础列表。 该算法基于每次改变时更新改变节点的权重。
