假设我的 vector/列表中有 30000 个对象。我一个一个补充。
我需要对它们进行分类。
一次对所有对象进行排序(如 std::sort)更快，还是在逐个添加对象时保持 vector/列表排序更快？
以后不会修改 vector/列表。
最佳答案
当你在一个一个地插入元素的同时保持你的 vector 列表排序时，你基本上是在执行插入排序，理论上在最坏的情况下运行 O(n^2)。平均情况也是二次的，这使得插入排序对于对大型数组进行排序不切实际。
输入 ~30000 后，最好获取所有输入，然后使用更快的排序算法对其进行排序。
编辑: 正如@Veritas 指出的那样，我们可以使用更快的算法来搜索元素的位置(如二进制搜索)。所以整个过程将花费 O(nlg(n)) 时间。 虽然，也可以指出，这里插入元素也是一个需要考虑的因素。如果我们想保持数组排序，插入元素的最坏情况需要 O(n^2)，这仍然是整体运行时间。
输入后排序仍然是更好的方法，而不是在每次迭代后保持排序。
关于c++ - 在插入时保持 std vector/列表排序，或对所有排序，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/22946772/