插入时让标准向量/列表保持排序，或全部排序 [英] keep std vector/list sorted while insert, or sort all

问题描述

让我们说我的向量/列表中有30000个对象.我一个接一个地添加.
我需要对它们进行排序.
一次对所有对象进行排序(如std :: sort)，还是在对对象进行逐一添加时保持向量/列表的排序速度更快?

Lets say I have 30000 objects in my vector/list. Which I add one by one.
I need them sorted.
Is it faster to sort all at once (like std::sort), or keep vector/list sorted while I add object one by one?

向量/列表以后将不会修改.

vector/list WILL NOT be modified later.

推荐答案

在向量列表一一插入的同时保持向量列表的排序时，基本上就是在执行插入排序，理论上，它在O(n ^ 2)中运行最糟糕的情况.平均情况也是二次的，这使得插入排序不适用于对大型数组进行排序.

When you are keeping your vector list sorted while inserting elements one by one , you are basically performing an insertion sort, that theoretically runs O(n^2) in worst case. The average case is also quadratic, which makes insertion sort impractical for sorting large arrays.

输入约30000时，最好先提取所有输入，然后使用更快的排序算法对其进行排序.

With your input of ~30000 , it will be better to take all inputs and then sort it with a faster sorting algorithm.

正如@Veritas指出的那样，我们可以使用更快的算法来搜索元素的位置(如二进制搜索).因此，整个过程将花费O(nlg(n))时间. 但是，也可能需要指出的是，在此处插入元素也是要考虑的因素.如果要保持数组排序，则插入元素的最坏情况是O(n ^ 2)，它仍然是整体运行时间.

As @Veritas pointed out, We can use faster algorithm to search the position for the element (like binary search). So the whole process will take O(nlg(n)) time. Though , It may also be pointed that here inserting the elements is also a factor to be taken into account. The worst case for inserting elements takes O(n^2) that is still the overall running time if we want to keep the array sorted.

到目前为止，输入排序仍然是更好的方法，而不是在每次迭代后对其进行排序.

Sorting after input is still by far the better method rather than keeping it sorted after each iteration.

这篇关于插入时让标准向量/列表保持排序，或全部排序的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！