logo标签列表

为什么Java中没有SortedList？

javasortingcollections
622

在Java中，有 SortedSet 和 SortedMap 两个接口。它们都属于Java集合框架，提供了一种排序访问元素的方式。

然而，在我的理解中，Java中没有SortedList。可以使用java.util.Collections.sort()对列表进行排序。

为什么Java没有设计SortedList呢？您有什么想法吗？

3
这个链接是否对你有帮助？ - Nico Haase
9
当你在列表中间插入一个元素时，你希望得到什么样的结果？ - bestsss
6
完全可以创建一个SortedList类，该类不实现java.util.List接口。把问题看作是对没有支持所需功能的数据结构进行的询问。不要被像命名这样微不足道的细节所分散注意力。 - Alderath
@Alderath，通常的结构是树（红黑树、AVL树或B树），带有额外的prev/next链接来支持排序。我使用类似的红黑树结构，带有prev/next链接。虽然它是一个相当小众的用途，但树可以按顺序遍历和插入顺序，具有O(logn)的查找/包含，但get(int)是O(n)的。考虑到它的小众适用性，我认为如果需要，开发人员应该自己实现一个。 - bestsss
6
不回答“为什么”的问题，但对于TreeSet来说，最简单的解决方法是使用一个永远不会返回零的比较器，例如int diff = this.score - that.score;``return (diff == 0) ? 1 : diff;。由于这是一种不好的做法，建议将其作为匿名构造函数参数提供，而不是实现Comparable接口。 - earcam
显示剩余4条评论
14个回答
1
我认为以上所有内容都没有回答这个问题，原因如下：
  1. 由于可以使用其他集合（例如 TreeSet、Collections、PriorityQueue 等）实现相同的功能（但这是一种替代方式，也会施加它们自己的限制，即 Set 将删除重复元素。简单地说，即使它不施加任何约束，它也不能回答为什么 Java 社区没有创建 SortedList 的问题）。
  2. 由于列表元素没有实现 compare/equals 方法（这对 Set 和 Map 也适用，在一般情况下，项目不实现 Comparable 接口，但当我们需要这些项目按排序顺序排列并想要使用 TreeSet/TreeMap 时，项目应实现 Comparable 接口）。
  3. 由于列表使用索引，而由于排序，它无法工作（这可以通过引入中间接口/抽象类来轻松处理）。
但是，没有人告诉我们确切的原因。我认为这种问题最好由 Java 社区本身回答，因为它只有一个具体的答案。但让我尽力回答如下：
正如我们所知，排序是一项昂贵的操作，而List和Set/Map之间有一个基本的区别，即List可以有重复项，而Set/Map则不行。这就是为什么我们在TreeSet/TreeMap中得到了Set/Map的默认实现的核心原因。在内部，这是一棵红黑树，每个操作（插入/删除/搜索）的复杂度都为O(log N)，而由于重复项，List无法适应这种数据存储结构。
现在问题出现了，我们也可以为List选择一个默认的排序方法，比如用复杂度为O(N log N)的MergeSort来排序，这是由Collections.sort(list)方法使用的。社区故意没有这样做，因为对于非唯一元素，我们有多种排序算法可供选择，如QuickSort、ShellSort、RadixSort等等。未来可能会有更多选择。而且有时相同的排序算法在排序的数据不同的情况下表现也不同。因此，他们希望保持这个选项开放，并留给我们自己选择。但对于Set/Map来说，O(log N)是最佳的排序复杂度。
0
我们有一个方法叫做 Collections.sort(arr)，它可以帮助对 ArrayList arr 进行排序。如果要按降序排列，我们可以使用 Collections.sort(arr, Collections.reverseOrder())。
0

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

考虑使用索引树映射。它是增强版JDK的TreeSet，提供了通过索引访问元素以及在不迭代或隐藏基础列表支持树的情况下查找元素索引的功能。该算法基于每次更改时更新更改节点的权重。
0
从计算的角度来看，简单的列表中，有序插入比无序插入再排序要更昂贵。
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接