algorithm - : sort n elements, 或在正确的位置一个接一个地插入 n 个元素哪个更快？

Question

一般来说，在某个集合中插入N个元素然后排序，或者在插入前找出元素的正确位置并准确插入该位置(重复N次)哪个更好？

Answer 1

它非常依赖所使用的数据结构和应用程序。

请注意，在数组 中插入一个元素需要将所有后续元素向右移动，这导致插入的时间复杂度为O(n)。
一个Binary Search Tree然而，允许在 O(logn) 中插入，但小于 cache比数组更高效 - 因此速度更慢。

另一方面，插入然后排序的结果 latency 在插入最后一个元素后 [O(nlogn) 排序]。
此外 - 如果您要经常查询 - 但很少添加元素 - 您希望避免过于频繁地排序 - 保持元素有序是实现此目的的简单方法。