受到这个问题的启发。
我的决定
#include <vector>
#include <string>
#include <algorithm>
#include <iostream>
#include <iomanip>
using namespace std;
int main(int argc, char * argv[])
{
vector<int> v(36000000);
int k = 0;
for(int i = 1; i <= 6000; ++i)
for(int j = 6001; j <= 12000; ++j)
v[k++] = i*j;
sort(v.begin(),v.end());
long long s = 0;
for(int i = 0; i < 36000000; ++i) s += v[i];
cout << s;
}
工作原理与 Python 中最好的差不多，但速度稍慢。在我的机器上，这一切都计为大约 2.04±0.01 秒。好吧，这不可能是 C ++ 不如 Python :) - 我开始尝试以各种方式加速这段代码。
无法优化，一切都依赖于sort. 带着悲伤，我把它换成了stable_sort——看看会发生什么，然后——你瞧！— 时间下降到 1.30±0.03 秒。
似乎一直有人说，在一般情况下，由于更大的复杂性stable_sort（不仅是算法，它等于O(N·log(N) 2）），它的效果更差sort。但是，事实证明，至少并非总是如此？我知道常数可能会有很大的不同:)，但是它什么时候小于常数sort？
在 G++ 下进行了检查-差异略有不同，但通常相同：1和2。
没有人对此进行深入研究，无法发表评论，如果两种功能都适合您，什么时候应用更有效？
视觉 C++ 2019，Windows 10
所有最好的排序算法都有复杂性
O(N * log(N))。Python 变得更快，因为它使用了 TimSort，并且当数组由排序的部分组成时，它的运行速度非常快。在上面的双循环中得到的正是这个数组。std::sort通常在大型数组上使用 QuickSort。这种排序没有利用数组部分已经排序的事实，在第一次迭代时它会破坏数组的结构。std::stable_sort通常使用 MergeSort，它O(n)比 QuickSort 需要更多的内存。正是由于额外的内存，默认使用了不稳定的排序。也许在 MergeSort 的 C++ 实现中，有一个优化可以检查子数组是否已经排序。在这种情况下，InsertionSort 可能不适用于小型子数组（检查子数组是否已经排序需要时间
O(n)，而 InsertionSort 需要O(n^2)时间）。如果子数组大小小于某个长度，则所有 3 种排序（TimSort、QuickSort、MergeSort）在内部使用插入排序。
用于比较的基准，
sort由stable_sort@wololo 提供，并由我稍作修改：该函数
int rand(int bits)生成一个随机数的bits位长。出于某种原因，数字的长度会影响排序的速度。这是我得到的（Visual C++ 2019，Windows 10）：