在插入项目或将它们添加到排序列表后对列表进行排序是否更快

如果我有一个排序列表(比如快速排序),如果我要添加很多值,最好暂停排序,将它们添加到最后,然后排序,或者使用二进制文件来正确放置项目添加它们.如果这些项目是随机的,或者已经或多或少的顺序,它会有所不同吗？

1> comingstorm..：

---

如果你添加了足够的项目,你有效地从头开始构建列表,你应该能够通过排序列表后获得更好的性能.

如果项目大部分都是有序的,你可以调整增量更新和定期排序以利用它,但坦率地说,它通常不值得麻烦.(你还需要注意一些事情,比如确保一些意想不到的顺序不能让你的算法花费更长的时间,qv天真快速排序)

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

如果不出意外,请记住有很多高度优化的批量排序可用.

2> Javier..：

---

通常使用堆更好.简而言之,它分割了推动者和拣选者之间维持秩序的成本.与大多数其他解决方案一样,这两个操作都是O(log n),而不是O(n log n).

---

如果列表是某种优先级队列,那么这是特别好的建议.谷歌在这种情况下表现不佳.

3> Mark Ransom..：

---

如果要添加串,则可以使用合并排序.对要添加的项目列表进行排序,然后从两个列表中复制,比较项目以确定下一个项目被复制.如果调整目标阵列大小并从最后向后工作,您甚至可以就地复制.

该解决方案的效率是O(n + m)+ O(m log m),其中n是原始列表的大小,m是要插入的项目的数量.

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

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

---

@MilesRout,根本不是真的.`m log m> m`,所以最好你可以简化它是'O(n +(m log m))`.

4> S.Lott..：

---

原则上，创建树比对列表进行排序要快。对于每个插入，树插入均为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和sort慢得多。

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

---

我会谨慎地说一棵树比一棵树快。它实际上取决于输入的大小和所使用的树实现。