创建矢量排序副本的更快方法

这个问题与C++没有什么特别的关系(除了使用“向量”这个词,它也存在于其他语言中)。因为这读起来像一个练习,我真的建议编写一个程序来测试它:

1. write a program that builds a vector of random N integers, v1
2. copy the vector to v2, via std::copy
3. time how long it takes to use insertion-sort (option 2 above), using a loop
4. time how long std::sort(v2, v2.begin(), v2.end()) takes

你可以用不同的计时器来计时,或者 <ctime> 标题或更新的 <chrono> 一个。见 this answer 作为替代品。

你应该发现,对于小尺寸的n,从第3步开始的循环比第4步快或者相当于第4步,从几百步开始, std::sort 变得越来越好。欢迎来到渐近复杂性和 big-o notation !

答案可以在下面的会议中找到:简而言之,这取决于向量的大小。因此彼得的评论是最好的。 CppCon 2018: Frederic Tingaud “A Little Order: Delving into the STL sorting algorithms”