Java 中的排序数组列表

Lists typically preserve the order in which items are added. Do you definitely need a list, or would a sorted set (e.g. TreeSet<E>) be okay for you? Basically, do you need to need to preserve duplicates?

Have a look at SortedList

This class implements a sorted list. It is constructed with a comparator that can compare two objects and sort objects accordingly. When you add an object to the list, it is inserted in the correct place. Object that are equal according to the comparator, will be in the list in the order that they were added to this list. Add only objects that the comparator can compare.

When the list already contains objects that are equal according to the comparator, the new object will be inserted immediately after these other objects.

Use java.util.PriorityQueue.

I think the choice between SortedSets/Lists and 'normal' sortable collections depends, whether you need sorting only for presentation purposes or at almost every point during runtime. Using a sorted collection may be much more expensive because the sorting is done everytime you insert an element.

If you can't opt for a collection in the JDK, you can take a look at the Apache Commons Collections

You could subclass ArrayList, and call Collections.sort(this) after any element is added - you would need to override two versions of add, and two of addAll, to do this.

Performance would not be as good as a smarter implementation which inserted elements in the right place, but it would do the job. If addition to the list is rare, the cost amortised over all operations on the list should be low.

Minimalistic Solution

Here is a quick and dirty solution.

class SortedArrayList<T> extends ArrayList<T> {
@SuppressWarnings("unchecked")
public void insertSorted(T value) {
int i = Collections.binarySearch((List<Comparable<T>>) this, value);
add(i < 0 ? -i - 1 : i, value);
}
}

Note that despite the binarySearch, insertSorted will run in linear time since add(index, value) runs in linear time for an ArrayList.

Inserting something non-comparable results in a ClassCastException. (This is the approach taken by PriorityQueue as well: A priority queue relying on natural ordering also does not permit insertion of non-comparable objects (doing so may result in ClassCastException).)

A more complete implementation would, just like the PriorityQueue, also include a constructor that allows the user to pass in a Comparator.

Demo

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);

....prints:

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

Overriding List.add

Note that overriding List.add (or List.addAll for that matter) to insert elements in a sorted fashion would be a direct violation of the interface specification.

From the docs of List.add:

boolean add(E e)
    Appends the specified element to the end of this list (optional operation).

Maintaining the sortedness invariant

Unless this is some throw-away code, you probably want to guarantee that all elements remain sorted. This would include throwing UnsupportedOperationException for methods like add, addAll and set, as well as overriding listIterator to return a ListIterator whose set method throws.

It might be a bit too heavyweight for you, but GlazedLists has a SortedList that is perfect to use as the model of a table or JList

You can try Guava's TreeMultiSet.

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

Since the currently proposed implementations which do implement a sorted list by breaking the Collection API, have an own implementation of a tree or something similar, I was curios how an implementation based on the TreeMap would perform. (Especialy since the TreeSet does base on TreeMap, too)

If someone is interested in that, too, he or she can feel free to look into it:

TreeList

Its part of the core library, you can add it via Maven dependency of course. (Apache License)

Currently the implementation seems to compare quite well on the same level than the guava SortedMultiSet and to the TreeList of the Apache Commons library.

But I would be happy if more than only me would test the implementation to be sure I did not miss something important.

Best regards!

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

I had the same problem. So I took the source code of java.util.TreeMap and wrote IndexedTreeMap. It implements my own IndexedNavigableMap:

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

The implementation is based on updating node weights in the red-black tree when it is changed. Weight is the number of child nodes beneath a given node, plus one - self. For example when a tree is rotated to the left:

    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 simply updates weights up to the root:

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

And when we need to find the element by index here is the implementation that uses weights:

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);
}

Also comes in very handy finding the index of a key:

    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;
}

You can find the result of this work at https://github.com/geniot/indexed-tree-map

TreeSet/TreeMap (as well as their indexed counterparts from the indexed-tree-map project) do not allow duplicate keys , you can use 1 key for an array of values. If you need a SortedSet with duplicates use TreeMap with values as arrays. I would do that.

Aioobe's approach is the way to go. I would like to suggest the following improvement over his solution though.

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's solution gets very slow when using large lists. Using the fact that the list is sorted allows us to find the insert point for new values using binary search.

I would also use composition over inheritance, something along the lines of

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

Just make a new class like this:

public class SortedList<T> extends ArrayList<T> {


private final Comparator<? super T> comparator;


public SortedList() {
super();
this.comparator = null;
}


public SortedList(Comparator<T> comparator) {
super();
this.comparator = comparator;
}


@Override
public boolean add(T item) {
int index = comparator == null ? Collections.binarySearch((List<? extends Comparable<? super T>>)this, item) :
Collections.binarySearch(this, item, comparator);
if (index < 0) {
index = index * -1 - 2;
}
super.add(index+1, item);
return true;
}


@Override
public void add(int index, T item) {
throw new UnsupportedOperationException("'add' with an index is not supported in SortedArrayList");
}


@Override
public boolean addAll(Collection<? extends T> items) {
boolean allAdded = true;
for (T item : items) {
allAdded = allAdded && add(item);
}
return allAdded;
}


@Override
public boolean addAll(int index, Collection<? extends T> items) {
throw new UnsupportedOperationException("'addAll' with an index is not supported in SortedArrayList");
}


}

You can test it like this:

    List<Integer> list = new SortedArrayList<>((Integer i1, Integer i2) -> i1.compareTo(i2));
for (Integer i : Arrays.asList(4, 7, 3, 8, 9, 25, 20, 23, 52, 3)) {
list.add(i);
}
System.out.println(list);