Java中的sorting数组列表

我很困惑,我找不到一个快速的答案。 我本质上是在Java中寻找一个实现了java.util.List接口的数据结构,但它按照sorting顺序存储它的成员。 我知道你可以使用一个正常的ArrayList并使用Collections.sort() ,但我有一个场景,我偶尔添加,并经常从列表中检索成员,我不想每次都sorting检索一个成员,以防一个新的被添加。 任何人都可以指向我在JDK甚至是第三方库中存在的东西吗?

编辑 :数据结构将需要保留重复。

答案的总结 :我发现这一切非常有趣,并且学到了很多东西。 Aioobe特别值得一提的是他在试图达到我上面的要求(主要是一个支持重复的sortingjava.util.List实现)的毅力。 我已经接受了他的答案,因为对于我所问的问题而言,他的答案是最准确的,而且即使我问的并不是我所需要的,我也多半想到了我所寻找的东西的含意。

我所要求的问题在于List接口本身以及接口中可选方法的概念。 引用javadoc:

这个接口的用户可以精确地控制每个元素插入到列表中的哪个位置。

插入到已sorting的列表中不能精确控制插入点。 然后,你必须考虑如何处理一些方法。 以add为例:

public boolean add(Object o)

  Appends the specified element to the end of this list (optional operation). 

你现在处于不舒服的情况1)打破合同,并实施加分的版本2)让add添加一个元素到列表的末尾,打破你的sorting顺序3)离开add (作为其可选的)通过抛出一个UnsupportedOperationException并实现另一种按sorting顺序添加项目的方法。

选项3可能是最好的,但我觉得它有一个不能使用的add方法和另一个不在接口中的sortedAdd方法。

其他相关解决scheme(无特定顺序):

  • java.util.PriorityQueue这可能是最接近我所需要的,而不是我所要求的。 在我的情况下,队列不是对象集合的最精确的定义,但是在function上它完成了我所需要的一切。
  • net.sourceforge.nite.util.SortedList 。 然而,这个实现通过在add(Object obj)方法中实现sorting来破坏List接口的契约,而奇怪地, add(int index, Object obj)没有效果方法。 一般共识build议throw new UnsupportedOperationException()在这种情况下可能是一个更好的select。
  • 番石榴的TreeMultiSet一个支持重复的集合实现
  • ca.odell.glazedlists.SortedList这个类在javadoc中有Warning: This class breaks the contract required by List

11 Solutions collect form web for “Java中的sorting数组列表”

简约的解决scheme

这是一个“最小”的解决scheme。

 class SortedArrayList<T> extends ArrayList<T> { @SuppressWarnings("unchecked") public void insertSorted(T value) { add(value); Comparable<T> cmp = (Comparable<T>) value; for (int i = size()-1; i > 0 && cmp.compareTo(get(i-1)) < 0; i--) Collections.swap(this, i, i-1); } } 

插入以线性时间运行,但无论如何,您将使用ArrayList(插入元素右侧的所有元素都必须以某种方式移动)。

在ClassCastException中插入一些不可比较的结果。 (这也是PriorityQueue采用的方法: 依赖于自然sorting的优先级队列也不允许插入不可比较的对象(这样做可能导致ClassCastException)。

重写List.add

请注意,重写List.add (或List.addAll )就可以直接违反接口规范 。 你可以做的是重写这个方法抛出一个UnsupportedOperationException

List.add的文档:

boolean add(E e)
将指定的元素附加到此列表的末尾(可选操作)。

同样的推理适用于两个版本的addaddAllset两个版本。 (所有这些都是根据列表界面的可选操作。)

一些testing

 SortedArrayList<String> test = new SortedArrayList<String>(); test.insertSorted("ddd"); System.out.println(test); test.insertSorted("aaa"); System.out.println(test); test.insertSorted("ccc"); System.out.println(test); test.insertSorted("bbb"); System.out.println(test); test.insertSorted("eee"); System.out.println(test); 

….打印:

 [ddd] [aaa, ddd] [aaa, ccc, ddd] [aaa, bbb, ccc, ddd] [aaa, bbb, ccc, ddd, eee] 

使用java.util.PriorityQueue

看看SortedList

这个类实现了一个sorting列表。 它是用比较器构build的,可以比较两个对象并相应地对对象进行sorting。 当你添加一个对象到列表中时,它被插入到正确的位置。 根据比较器相等的对象,将按照它们被添加到该列表的顺序在列表中。 仅添加比较器可以比较的对象。


当列表已经包含根据比较器相等的对象时,新对象将被立即插入到这些其他对象之后。

你可以尝试番石榴的 TreeMultiSet 。

  Multiset<Integer> ms=TreeMultiset.create(Arrays.asList(1,2,3,1,1,-1,2,4,5,100)); System.out.println(ms); 

列表通常保留添加项目的顺序。 你肯定需要一个列表 ,或者一个有序的集合 (比如TreeSet<E> )对你来说可以吗? 基本上,你需要保留重复吗?

这对你来说可能有点太重了,但是GlazedLists有一个SortedList ,可以很好地用作表或JList的模型

Aioobe的方法是要走的路。 我想build议他的解决scheme,但以下改善。

 class SortedList<T> extends ArrayList<T> { public void insertSorted(T value) { int insertPoint = insertPoint(value); add(insertPoint, value); } /** * @return The insert point for a new value. If the value is found the insert point can be any * of the possible positions that keeps the collection sorted (.33 or 3.3 or 33.). */ private int insertPoint(T key) { int low = 0; int high = size() - 1; while (low <= high) { int mid = (low + high) >>> 1; Comparable<? super T> midVal = (Comparable<T>) get(mid); int cmp = midVal.compareTo(key); if (cmp < 0) low = mid + 1; else if (cmp > 0) high = mid - 1; else { return mid; // key found } } return low; // key not found } } 

使用大型列表时,aioobe的解决scheme变得非常慢。 使用列表sorting的事实允许我们使用二分查找find新值的插入点。

我也将使用inheritance的组合,沿线的东西

 SortedList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable 

你可以inheritanceArrayList,并且在添加任何元素之后调用Collections.sort(this) – 你需要重写两个版本的add和两个addAll来做到这一点。

性能不如在适当的地方插入元素的更聪明的实现,但它可以完成这项工作。 如果增加清单是很less的,那么清单上所有操作的摊销成本应该很低。

我认为SortedSets / Lists和“普通”可sorting集合之间的select取决于您是否仅需要为了演示目的或几乎在运行时间的每个点进行sorting。 使用sorting后的集合可能会更加昂贵,因为每次插入元素时都会进行sorting。

如果你不能在JDK中select一个集合,你可以看看Apache Commons集合

由于目前提出的通过中断Collection API来实现sorting列表的实现,具有自己的树或类似的实现,所以我很好奇基于TreeMap的实现将如何执行。 (特别是TreeSet也是基于TreeMap的)

如果有人也对此感兴趣,他或她可以随意查看:

的TreeList

它是核心库的一部分,当然你可以通过Maven依赖关系添加它。 (Apache许可证)

目前这个实现似乎比guava SortedMultiSet和Apache Commons库的TreeList在相同的层次上相当好。

但是,如果不仅仅是我会testing执行,以确保我没有错过重要的事情,我会很高兴。

最好的祝福!

我有同样的问题。 于是我拿了java.util.TreeMap的源代码编写了IndexedTreeMap 。 它实现了我自己的IndexedNavigableMap

 public interface IndexedNavigableMap<K, V> extends NavigableMap<K, V> { K exactKey(int index); Entry<K, V> exactEntry(int index); int keyIndex(K k); } 

这个实现是基于在更改红黑树时更新节点权重。 权重是给定节点下面的子节点的数量,加上一个自我。 例如,当一棵树向左旋转时:

  private void rotateLeft(Entry<K, V> p) { if (p != null) { Entry<K, V> r = p.right; int delta = getWeight(r.left) - getWeight(p.right); p.right = r.left; p.updateWeight(delta); if (r.left != null) { r.left.parent = p; } r.parent = p.parent; if (p.parent == null) { root = r; } else if (p.parent.left == p) { delta = getWeight(r) - getWeight(p.parent.left); p.parent.left = r; p.parent.updateWeight(delta); } else { delta = getWeight(r) - getWeight(p.parent.right); p.parent.right = r; p.parent.updateWeight(delta); } delta = getWeight(p) - getWeight(r.left); r.left = p; r.updateWeight(delta); p.parent = r; } } 

updateWeight只是更新权重,直到根:

  void updateWeight(int delta) { weight += delta; Entry<K, V> p = parent; while (p != null) { p.weight += delta; p = p.parent; } } 

而当我们需要通过索引来查找元素时,这里是使用权重的实现:

 public K exactKey(int index) { if (index < 0 || index > size() - 1) { throw new ArrayIndexOutOfBoundsException(); } return getExactKey(root, index); } private K getExactKey(Entry<K, V> e, int index) { if (e.left == null && index == 0) { return e.key; } if (e.left == null && e.right == null) { return e.key; } if (e.left != null && e.left.weight > index) { return getExactKey(e.left, index); } if (e.left != null && e.left.weight == index) { return e.key; } return getExactKey(e.right, index - (e.left == null ? 0 : e.left.weight) - 1); } 

还有一个非常方便的find一个关键的索引:

  public int keyIndex(K key) { if (key == null) { throw new NullPointerException(); } Entry<K, V> e = getEntry(key); if (e == null) { throw new NullPointerException(); } if (e == root) { return getWeight(e) - getWeight(e.right) - 1;//index to return } int index = 0; int cmp; index += getWeight(e.left); Entry<K, V> p = e.parent; // split comparator and comparable paths Comparator<? super K> cpr = comparator; if (cpr != null) { while (p != null) { cmp = cpr.compare(key, p.key); if (cmp > 0) { index += getWeight(p.left) + 1; } p = p.parent; } } else { Comparable<? super K> k = (Comparable<? super K>) key; while (p != null) { if (k.compareTo(p.key) > 0) { index += getWeight(p.left) + 1; } p = p.parent; } } return index; } 

您可以在http://code.google.com/p/indexed-tree-map/find这项工作的结果&#x3002;

TreeSet / TreeMap(以及来自索引树映射项目的索引对应项)不允许重复的键,您可以使用1个键作为值的数组。 如果你需要一个带有重复项的SortedSet,使用TreeMap的值作为数组。 我会这样做的。

  • 如何在一列中对MATLAB中的二维数组进行sorting?
  • 为什么quicksort比mergesort更好?
  • 如何在ruby中对散列数组进行sorting
  • GridViewsorting:SortDirection始终为升序
  • 如何sortingJava中的对象数组?
  • 在PHP中sorting对象
  • Microsoft SQL 2005中的自然(人类字母数字)sorting
  • 在MySQL中对varchar字段进行数字sorting
  • 通过字段名称sortingnamedtuples列表的Pythonic方法
  • 对n个第一个元素已经sorting的向量进行sorting?
  • 如何在Java中对ArrayList进行sorting