algorithm - 插入项目或将它们添加到排序列表后排序列表是否更快

Question

如果我有一个排序列表（比如要排序的快速排序），如果我要添加很多值，最好暂停排序，并将它们添加到末尾，然后排序，或者使用二进制印章正确放置项目，同时添加它们。如果这些项目是随机的，或者已经或多或少按顺序排列，这会有所不同吗？

score 46 · Accepted Answer

如果您添加了足够多的项目以有效地从头开始构建列表，那么您应该能够通过事后对列表进行排序来获得更好的性能。

如果项目大部分是有序的，您可以调整增量更新和定期排序以利用这一点，但坦率地说，这通常不值得麻烦。（你还需要小心一些事情，比如确保一些意外的排序不会让你的算法花费更长的时间，qv naive quicksort）

增量更新和常规列表排序都是 O(N log N) 但是你可以得到一个更好的常数因子排序之后的所有内容（我在这里假设你有一些辅助数据结构，所以你的增量更新可以比 O 更快地访问列表项（N）...）。一般来说，一次性排序比保持增量排序具有更多的设计自由度，因为增量更新必须始终保持完整的顺序，而一次性批量排序则不需要。

如果不出意外，请记住有许多高度优化的批量排序可用。

score 27 · Accepted Answer

通常使用堆要好得多。简而言之，它将维持订单的成本分摊在推送者和拣选者之间。与大多数其他解决方案一样，这两个操作都是 O(log n)，而不是 O(n log n)。

score 11 · Accepted Answer

如果要添加成束，则可以使用合并排序。对要添加的项目列表进行排序，然后从两个列表中复制，比较项目以确定接下来要复制的项目。如果调整目标数组的大小并从头向后工作，您甚至可以就地复制。

此解决方案的效率为 O(n+m) + O(m log m)，其中 n 是原始列表的大小，m 是要插入的项目数。

编辑：由于这个答案没有得到任何爱，我想我会用一些 C++ 示例代码来充实它。我假设排序列表保存在链表而不是数组中。这将算法更改为看起来更像是插入而不是合并，但原理是相同的。

// Note that itemstoadd is modified as a side effect of this function
template<typename T>
void AddToSortedList(std::list<T> & sortedlist, std::vector<T> & itemstoadd)
{
    std::sort(itemstoadd.begin(), itemstoadd.end());
    std::list<T>::iterator listposition = sortedlist.begin();
    std::vector<T>::iterator nextnewitem = itemstoadd.begin();
    while ((listposition != sortedlist.end()) || (nextnewitem != itemstoadd.end()))
    {
        if ((listposition == sortedlist.end()) || (*nextnewitem < *listposition))
            sortedlist.insert(listposition, *nextnewitem++);
        else
            ++listposition;
    }
}

score 4 · Accepted Answer

原则上，创建树比排序列表更快。每个插入的树插入为 O(log(n))，导致总体 O(n log(n))。在 O(n log(n)) 中排序。

这就是 Java 具有 TreeMap 的原因（除了 List 的 TreeSet、TreeList、ArrayList 和 LinkedList 实现之外。）

TreeSet 将事物保持在对象比较顺序中。键由 Comparable 接口定义。
LinkedList 将事物保持在插入顺序中。
ArrayList 使用更多内存，对于某些操作来说更快。
类似地，TreeMap 消除了按键排序的需要。该映射在插入期间按键顺序构建，并始终按排序顺序维护。

但是，出于某种原因，TreeSet 的 Java 实现比使用 ArrayList 和排序要慢很多。

[很难推测为什么它会显着变慢，但确实如此。一次通过数据应该会稍微快一些。这种事情往往是内存管理的成本胜过算法分析。]

score 4 · Accepted Answer

我会说，让我们测试一下！:)

我尝试使用快速排序，但使用快速排序对几乎排序的数组进行排序是……好吧，这不是一个好主意。我尝试了一个修改过的，截断了 7 个元素并为此使用了插入排序。仍然，可怕的表现。我切换到合并排序。它可能需要相当多的内存进行排序（它不是就地的），但排序数组的性能要好得多，随机数组的性能几乎相同（两者的初始排序几乎相同，快速排序只是稍微快一点）。

这已经表明了一件事：您的问题的答案很大程度上取决于您使用的排序算法。如果它在几乎排序的列表上表现不佳，在正确的位置插入会比在末尾添加然后重新排序要快得多；并且合并排序可能不是您的选择，因为如果列表很大，它可能需要太多的外部内存。顺便说一句，我使用了一个自定义合并排序实现，它只使用 1/2 的外部存储来实现天真的实现（它需要与数组大小本身一样多的外部存储）。

如果合并排序不是选项并且快速排序肯定不是选项，那么最好的选择可能是堆排序。

我的结果是：在末尾简单地添加新元素，然后重新排序数组比将它们插入到正确的位置要快几个数量级。但是，我的初始数组有 10 个 mio 元素（已排序），而我正在添加另一个 mio（未排序）。因此，如果您将 10 个元素添加到 10 个 mio 的数组中，正确插入它们比重新排序所有内容要快得多。因此，您的问题的答案还取决于初始（已排序）数组有多大以及您要添加多少新元素。

score 1 · Accepted Answer

差不多。将一个项目插入排序列表是 O(log N)，并且对列表中的每个元素 N 执行此操作（从而构建列表）将是 O(N log N)，这是快速排序（或合并排序）的速度更接近这种方法）。

如果您将它们插入到前面，它将是 O(1)，但之后进行快速排序，它仍然是 O(N log N)。

我会采用第一种方法，因为它有可能会稍微快一些。如果列表的初始大小 N 远大于要插入的元素数 X，则插入方法为 O(X log N)。插入到列表头部后的排序是 O(N log N)。如果 N=0（即：你的列表最初是空的），则按排序顺序插入或之后排序的速度是相同的。

score 1 · Accepted Answer

如果列表 a) 已经排序，并且 b) 本质上是动态的，那么插入排序列表应该总是更快（找到正确的位置 (O(n)) 并插入 (O(1))）。

但是，如果列表是静态的，则必须对列表的其余部分进行洗牌（O(n) 找到正确的位置，O(n) 向下滑动）。

无论哪种方式，插入排序列表（或类似二叉搜索树）应该更快。

O(n) + O(n) 应该总是比 O(N log n) 快。

score 1 · Accepted Answer

将项目插入排序列表需要O(n)时间，而不是O(log n)时间。您必须花时间找到放置它的地方O(log n)。但是你必须转换所有的元素——花O(n)时间。因此，在保持排序的同时插入是O(n ^ 2)，而将它们全部插入然后排序是O(n log n)。

根据您的排序实现，您可以获得比O(n log n)插入数量远小于列表大小的情况更好的结果。但如果是这样的话，无论哪种方式都无关紧要。

如果插入的数量很大，请执行全部插入和排序解决方案，否则可能无关紧要。

score 1 · Accepted Answer

在较高的层次上，这是一个非常简单的问题，因为您可以将排序视为迭代搜索。当您想将一个元素插入到有序数组、列表或树中时，您必须搜索插入它的点。然后你把它放进去，希望成本低。所以你可以把排序算法想象成只是把一堆东西一个一个地寻找合适的位置并插入它们。因此，插入排序（O（n * n））是迭代线性搜索（O（n））。树、堆、合并、基数和快速排序 (O(n*log(n))) 可以被认为是迭代二进制搜索 (O(log(n)))。如果底层搜索是 O(1)，就像在有序哈希表中一样，则可以进行 O(n) 排序。（这方面的一个例子是通过将 52 张卡片扔到 52 个垃圾箱中来对它们进行分类。）

所以你的问题的答案是，一次插入一个东西，而不是保存它们然后对它们进行排序，在大 O 意义上应该没有太大区别。当然，您可能需要处理恒定的因素，而这些因素可能很重要。

当然，如果 n 很小，比如 10，那么整个讨论都是愚蠢的。

score 0 · Accepted Answer

您应该先添加它们，然后使用基数排序，这应该是最佳的

http://en.wikipedia.org/wiki/Radix_sort#Efficiency

score 0 · Accepted Answer

（如果您正在谈论的列表类似于 C# List<T>。）将一些值添加到具有许多值的排序列表中的正确位置将需要更少的操作。但是，如果要添加的值的数量变大，则需要更多。

我建议您不要使用列表，而是使用一些更合适的数据结构。比如二叉树。插入时间最短的排序数据结构。

score -1 · Accepted Answer

如果这是 .NET 并且项目是整数，则将它们添加到 Dictionary 会更快（或者如果您使用 .Net 3.0 或更高版本，如果您不介意丢失重复项，请使用 HashSet）这为您提供了自动排序。

我认为字符串也会以同样的方式工作。美妙之处在于您以这种方式获得 O(1) 插入和排序。

score -2 · Accepted Answer

将一个项目插入排序列表是 O(log n)，而对列表进行排序是 O(n log N) 这表明最好先排序然后插入

但是请记住，大“O”只涉及速度与项目数量的比例关系，对于您的应用程序来说，中间的插入可能是昂贵的（例如，如果它是一个向量），因此之后的附加和排序可能会更好。

algorithm - 插入项目或将它们添加到排序列表后排序列表是否更快

13 回答 13

Related

Reference