performance - 在经常插入排序的列表中插入项目

Question

我有一个经常插入排序的列表。是否有一个好的位置（除了结尾）可以添加到这个列表中以最小化插入排序必须做的工作？

Answer 1

插入的最佳位置是元素在排序列表中所属的位置。这将类似于抢先插入排序。

Answer 2

你的问题没有意义。列表是插入排序的（这意味着您不能根据定义追加到末尾；元素仍将在它所属的位置结束。否则，列表不会被排序）。

如果您必须添加大量元素，那么最好的解决方案是克隆列表，添加所有元素，对新列表进行一次排序，然后用克隆替换第一个列表。

[编辑] 回复您的评论：在进行了几次追加后，您必须先对列表进行排序，然后才能进行下一次排序插入。所以问题不在于如何使排序插入更便宜，而是追加和排序插入之间的排序。

答案是大多数排序算法对部分排序的列表都做得很好。你需要问的问题是：使用什么排序算法，它有什么属性，最重要的是，你为什么要关心。

最后一个问题意味着您应该在进行任何类型的优化之前测量性能，因为除非它基于实际数字，否则您有 90% 的机会伤害大于帮助。

回到排序。Java 使用一个版本的快速排序来对集合进行排序。快速排序将选择一个枢轴元素来对集合进行分区。这种选择对于算法的性能至关重要。为了获得最佳性能，枢轴元素应尽可能靠近结果中间的元素。通常，快速排序使用当前分区中间的元素作为枢轴元素。此外，快速排序将开始处理具有小索引的列表。

因此，在最后添加新元素可能不会给您带来良好的性能。它不会影响枢轴元素选择，但快速排序会在检查完所有已排序元素后查看新元素。在中间添加新元素会影响枢轴选择，我们无法真正判断这是否会对性能产生影响。我的直觉猜测是，如果快速排序在分区中间找到已排序的元素，则枢轴元素会更好。

这使得在开始时添加新元素。这样，快速排序通常会找到一个完美的枢轴元素（因为将排序列表的中间部分）并且它会首先选择新元素。缺点是每次插入都必须复制整个数组。有两种方法可以避免这种情况：a)正如我在其他地方所说，今天的 PC 几乎可以立即复制大量 RAM，因此您可以忽略这个小的性能损失。b）您可以使用第二个 ArrayList，将所有新元素放入其中，然后使用addAll(). Java 将针对这种情况在内部进行一些优化，并且只需移动现有元素一次。

[EDIT2] 我完全误解了你的问题。对于算法插入排序，最好的地方可能是中间的某个地方。这应该将您必须在整个列表中移动元素的机会减半。但由于我不是 100% 确定，我建议创建几个小测试来验证这一点。