Ste*_*eve 64 sorting algorithm list
如果我有一个排序列表(比如快速排序),如果我要添加很多值,最好暂停排序,将它们添加到最后,然后排序,或者使用二进制文件来正确放置项目添加它们.如果这些项目是随机的,或者已经或多或少的顺序,它会有所不同吗？
com*_*orm 33
如果你添加了足够的项目,你有效地从头开始构建列表,你应该能够通过排序列表后获得更好的性能.
如果项目大部分都是有序的,你可以调整增量更新和定期排序以利用它,但坦率地说,它通常不值得麻烦.(你还需要注意一些事情,比如确保一些意想不到的顺序不能让你的算法花费更长的时间,qv天真快速排序)
增量更新和常规列表排序都是O(N log N),但是你可以获得一个更好的常量因子,然后排序所有内容(我假设你有一些辅助数据结构,所以你的增量更新可以比O更快地访问列表项(N)...).一般来说,一次性排序比增加维护顺序具有更多的设计自由度,因为增量更新必须始终保持完整的顺序,但一次性批量排序则不然.
如果不出意外,请记住有很多高度优化的批量排序可用.
Mar*_*som 10
如果要添加串,则可以使用合并排序.对要添加的项目列表进行排序,然后从两个列表中复制,比较项目以确定下一个项目被复制.如果调整目标阵列大小并从最后向后工作,您甚至可以就地复制.
该解决方案的效率是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;
}
}
原则上，创建树比对列表进行排序要快。对于每个插入，树插入均为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慢得多。
[很难推测为什么它会显着变慢，但是确实如此。一遍遍数据应该稍微快一点。这种事情通常是内存管理的成本超过算法分析的成本。]
我想说，我们来测试一下吧！:)
我尝试过使用快速排序，但是使用快速排序对几乎排序的数组进行排序......好吧，这并不是一个好主意。我尝试了一种修改后的方法，截断 7 个元素并使用插入排序。尽管如此，表现还是很糟糕。我切换到合并排序。它可能需要相当多的内存来进行排序（它不是就地排序），但是排序数组的性能要好得多，而随机数组的性能几乎相同（初始排序两者花费的时间几乎相同，快速排序仅稍快一些） ）。
这已经表明了一件事：您问题的答案在很大程度上取决于您使用的排序算法。如果它在几乎已排序的列表上性能较差，则在正确的位置插入会比在末尾添加然后重新排序要快得多；合并排序可能不适合您，因为如果列表很大，它可能需要太多的外部内存。顺便说一句，我使用了自定义合并排序实现，它仅使用原始实现的 1/2 外部存储（需要与数组大小本身一样多的外部存储）。
如果合并排序不可行并且快速排序也肯定不可行，那么最好的替代方案可能是堆排序。
我的结果是：简单地在末尾添加新元素，然后对数组重新排序比将它们插入到正确的位置要快几个数量级。然而，我的初始数组有 10 个 mio 元素（已排序），我正在添加另一个 mio（未排序）。因此，如果将 10 个元素添加到 10 mio 的数组中，正确插入它们比重新排序所有内容要快得多。因此，您问题的答案还取决于初始（已排序）数组有多大以及您要向其中添加多少个新元素。