Java中的排序数组列表

Java中的排序数组列表 简约解决方案

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

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

：
依赖自然顺序的优先级队列也不允许插入不可比较的对象（这样做可能会导致ClassCastException）。 ）

覆写

List.add

请注意，以排序的方式覆盖

List.add

（或

List.addAll

为此）插入元素将
直接违反接口规范 。您 可以 做的是重写此方法以引发

UnsupportedOperationException

。

来自的文档

List.add

：

boolean add(E e)

将指定的元素追加到此列表的末尾（可选 *** 作）。

同样的道理也适用于这两个版本

add

，两个版本的

addAll

和

set

。（根据列表界面，所有这些都是可选 *** 作。）

一些测试

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]