从头开始排序列表

Question

我有一个需要大量添加/删除的对象列表。我希望根据某个功能对列表进行排序。

现在，每次我添加一个新对象时，我都会：

list.add(obj1);
Collections.sort(list1, comparator);

删除对象不会“取消排序”列表，因此我只需要为添加操作执行此操作。

但是，Collections.sortO(>N) 不是很快。

java中是否有任何结构允许我从一开始就保留一个排序列表？

忘了提

我尝试使用TreeSet. 它允许我传递一个比较器，该比较器将用于排序，但也将用于删除我不想要的元素。我希望它被排序，但删除功能与列表相同。

Answer 1

正如Alencar建议的那样，使用Collections.binarySearch(yourList, key, comparator)找到正确的插入位置。这比查找整个列表要快得多，因为binarySearch只需要 log2（列表大小）查询即可找到正确的插入位置。所以，如果你的插入代码是void sortedInsert(List<T> list, T value, Comparator<T> comparator) {&nbsp; int pos=0;&nbsp; ListIterator<T> it=list.listIterator();&nbsp; while (it.hasNext() && comparator.compare(value, it.next()) < 0) pos ++;&nbsp; if (pos < it.previousIndex()) it.previous();&nbsp; it.add(value);}...更快的版本将是...void sortedInsert2(List<T> list, T value, Comparator<T> comparator) {&nbsp; int pos = Collections.binarySearch(list, value, comparator);&nbsp; if (pos < 0) {&nbsp; &nbsp; &nbsp;pos = -pos -1; // returns negatives if not found; see javadoc&nbsp; }&nbsp; list.insert(value, pos);}请注意，差异可能不是那么大，因为插入非链表需要向上移动元素。因此，如果基础列表是ArrayList，则平均而言，将一半的元素复制到右侧一个位置以为新元素腾出位置会导致O(n)每次复制额外的时间。如果列表是链接的，你仍然需要付出代价O(n)，但这次是执行二分搜索——在这种情况下，使用第一个版本可能会更好。请注意，第一个版本使用 aListIterator以防您决定使用链表。对于，使用和ArrayLists会更容易，但在迭代链表的上下文中，这是一个非常糟糕的主意。list.get(pos)list.add(pos, value)

Answer 2

你不能在“正确”的地方添加对象吗？已经排序了吗？您说过每次添加新对象时都会对列表/集合进行排序。也许您可以使用二进制搜索来查找插入新值所需的确切索引或使用比较器来查找。