algorithm - 什么更快：对 n 个元素进行排序，或将 n 个元素一一插入正确的位置？

Question

一般来说，什么更好：在某个集合中插入N个元素然后对其进行排序，或者在插入之前找出元素的正确位置并将其准确插入该位置（重复N次）？

score 6 · Accepted Answer

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

请注意，在数组中插入一个元素需要将所有以下元素向右移动，这会导致O(n)插入。
然而，二叉搜索树允许插入O(logn)，但缓存效率低于数组 - 因此速度较慢。

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

score 1 · Accepted Answer

在不对输入做任何假设的情况下，排序需要 nlog(n) 时间。插入一个元素需要 O(n) 时间（链表）。因此，在所有插入后排序更快。

score 1 · Accepted Answer

这个更好

“在某个集合中插入 N 个元素，然后对其进行排序”

因为可以使用O(nlogn)算法进行排序。像这样在哪里

“在插入之前找出元素的正确位置并将其准确插入该位置（重复N次）？”

是插入排序，以最坏的情况而闻名O(n^2)。

也就是说，插入排序是在线算法。即你不需要提前知道整个数据来开始排序。考虑由其他并行运行的程序生成的数据。这里插入排序是有意义的。而另一种方法需要整个数据到位。

score 0 · Accepted Answer

取决于你的数据结构。请注意，要在插入之前找出正确的位置，您必须以某种方式对元素进行排序，这要求它们已经存储在数据结构中。您能否提供有关您要实现的目标的更多信息？

4 回答 4