Java 中的排序数组列表

列表通常保留添加项的顺序。你肯定需要一个列表，还是一个排序的集合（例如 TreeSet<E>）对你来说没问题？基本上，您需要保留重复项吗？

看一看 SortedList

此类实现排序列表。它由一个比较器构成，可以比较两个对象并相应地对对象进行排序。将对象添加到列表中时，该对象将插入到正确的位置。根据比较器相等的对象将按照它们添加到此列表中的顺序在列表中。仅添加比较器可以比较的对象。

---

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

使用 java.util.PriorityQueue。

我认为 SortedSets/Lists 和“普通”可排序集合之间的选择取决于，您是仅出于演示目的而需要排序，还是在运行时的几乎每个点都需要排序。使用排序集合的成本可能要高得多，因为每次插入元素时都会进行排序。

如果您无法在 JDK 中选择集合，可以查看 Apache Commons 集合

您可以对 ArrayList 进行子类化，并在添加任何元素后调用 Collections.sort（this） - 您需要覆盖两个版本的 add 和两个版本的 addAll 才能做到这一点。

性能不如在正确位置插入元素的更智能的实现，但它可以完成这项工作。如果很少添加到列表中，则清单上所有操作的摊销成本应该很低。

简约解决方案

这是一个快速而肮脏的解决方案。

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

请注意，尽管 ，将以线性时间运行，因为 .binarySearchinsertSortedadd(index, value)ArrayList

插入不可比较的内容会导致 ClassCastException。（这也是 PriorityQueue 采用的方法：依赖于自然排序的优先级队列也不允许插入不可比较的对象（这样做可能会导致 ClassCastException）。)

一个更完整的实现，就像 一样，还包括一个构造函数，允许用户传入 .PriorityQueueComparator

演示

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]

重写List.add

请注意，重写 List.add（或 List.addAll）以排序方式插入元素将直接违反接口规范。

来自以下文档：List.add

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

保持排序不变性

除非这是一些一次性代码，否则您可能希望保证所有元素都保持排序。这将包括抛出 和 等方法，以及重写以返回 who 方法抛出。UnsupportedOperationExceptionaddaddAllsetlistIteratorListIteratorset

它对你来说可能有点太重量级了，但 GlazedLists 有一个 SortedList，非常适合用作表或 JList 的模型

您可以尝试 Guava 的 TreeMultiSet。

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

由于目前提议的实现确实通过破坏集合 API 来实现排序列表，并且有自己的树或类似的东西的实现，因此我很好奇基于 TreeMap 的实现将如何执行。（特别是因为 TreeSet 也基于 TreeMap）

如果有人也对此感兴趣，他或她可以随时研究一下：

树列表

它是核心库的一部分，当然你可以通过 Maven 依赖来添加它。（Apache 许可证）

目前，该实现似乎与番石榴 SortedMultiSet 和 Apache Commons 库的 TreeList 在同一级别上相当不错。

但是，如果不仅仅是我一个人测试实现以确保我没有错过重要的东西，我会很高兴。

此致敬意！

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

我也有同样的问题。于是我拿了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);
}

该实现基于在红黑树发生更改时更新节点权重。权重是给定节点下的子节点数，加上一个 - self。例如，当一棵树向左旋转时：

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

查找键的索引也非常方便：

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

您可以在以下位置找到这项工作的结果 https://github.com/geniot/indexed-tree-map

TreeSet/TreeMap（以及它们在 indexed-tree-map 项目中的索引对应项）不允许重复键，您可以将 1 个键用于值数组。如果您需要具有重复项的 SortedSet，请使用将值作为数组的 TreeMap。我会这样做的。

Aioobe的方法是要走的路。不过，我想对他的解决方案提出以下改进建议。

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 的解决方案在使用大型列表时会变得非常慢。利用列表排序的事实，我们可以使用二进制搜索找到新值的插入点。

我也会使用组合而不是继承，类似于

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

只需创建一个新类，如下所示：

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

}

你可以像这样测试它：

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

以下方法可用于打印 String 对象的 LinkedList 的元素。

该方法接受 LinkedList 对象作为输入，并将列表的每个元素（用空格分隔）打印到控制台。 为了使输出更具可读性，该方法还在列表前后添加换行符。

public static void printList(LinkedList<String> list) {
    System.out.println("\nList is: ");
    for (String element : list) {
        System.out.print(element + " ");
    }
    System.out.println();
}