java - 从头开始对列表进行排序

Question

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

现在，每次添加新对象时，我都会:

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

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

但是，Collections.sort 的时间复杂度为 O(>N)，速度不是很快。

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

忘了提及

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

Answer 1

如Alencar建议使用 Collections.binarySearch(yourList, key, comparator) 来查找正确的插入位置。这比查找整个列表要快得多，因为 binarySearch只需要log2(列表大小)查询即可找到正确的插入位置。

所以，如果您的插入代码是

void sortedInsert(List<T> list, T value, Comparator<T> comparator) {
  int pos=0;
  ListIterator<T> it=list.listIterator();
  while (it.hasNext() && comparator.compare(value, it.next()) < 0) pos ++;
  if (pos < it.previousIndex()) it.previous();
  it.add(value);
}

...更快的版本是...

void sortedInsert2(List<T> list, T value, Comparator<T> comparator) {
  int pos = Collections.binarySearch(list, value, comparator);
  if (pos < 0) {
     pos = -pos -1; // returns negatives if not found; see javadoc
  }
  list.insert(value, pos);
}

请注意，差异可能不会那么大，因为插入非链接列表需要向上移动元素。因此，如果底层列表是 ArrayList，则平均将一半元素复制到右侧一个位置来为新元素腾出位置，会产生额外的 O(n) 复杂度每个副本的时间。如果列表是链接的，您仍然需要支付 O(n) 惩罚，但这次要执行二分搜索 - 在这种情况下，使用第一个版本可能会更好。

请注意，第一个版本使用 ListIterator 以防万一您决定使用链接列表。对于 ArrayLists，使用 list.get(pos) 和 list.add(pos, value) 会更容易，但这些是在迭代链表的上下文中这是一个非常糟糕的主意。