创建 C++ 向量的排序副本的最高效方法是什么？

Question

给定一个 C++ 向量（假设它是双精度向量，我们称之为

unsorted

），创建包含

sorted

的排序副本的新向量

unsorted

的最高效方法是什么？

考虑以下简单的解决方案：

std::vector<double> sorted = unsorted;
std::sort(sorted.begin(), sorted.end());

此解决方案有两个步骤：

1. 创建

   unsorted

   的完整副本。
2. 排序。

但是，在步骤 1 的初始副本中可能会浪费大量精力，特别是对于（例如）已经大部分排序的大型向量。

如果我手动编写此代码，我可以将排序算法的第一遍与步骤 1 结合起来，方法是让第一遍从

unsorted

向量读取值，同时将它们写入

sorted

，根据需要进行部分排序。 。根据算法，后续步骤可能仅适用于

sorted

中的数据。

有没有办法用C++标准库、Boost或者第三方跨平台库来做这样的事情？

一个重要的一点是确保

sorted

C++ 向量的内存在排序开始之前不会不必要地初始化为零。许多排序算法需要立即随机写入访问

sorted

向量，因此使用

reserve()

和

push_back()

不适用于第一遍，但

resize()

会浪费时间初始化向量。

---

编辑：由于答案和评论不一定明白为什么“简单的解决方案”效率低下，请考虑

unsorted

数组实际上已经按排序顺序排列的情况（或者只需要一次交换即可排序） ）。在这种情况下，无论采用哪种排序算法，使用简单的解决方案，每个值都需要至少读取两次——一次在复制时，一次在排序时。但使用排序时复制的解决方案，读取次数可能会减半，因此性能大约增加一倍。当使用比

unsorted

更高效的排序算法（可能是 O(n) 而不是 O(n log n)）时，无论

std::sort

中的数据如何，都会出现类似的情况。

Answer 1

标准库故意没有提供复制时排序功能，因为复制的复杂度为 O(n)，而

std::sort

的复杂度为 O(n log n)。

因此，对于任何较大的 n 值，排序将完全主导成本。 （如果 n 很小，那也没关系）。

Answer 2

假设双精度数向量不包含 NAN 或无穷大等特殊数字，则双精度数可以被视为 64 位符号 + 幅度整数，可以将其转换为用于最快的基数排序。这些“符号+幅度整数”需要转换为 64 位无符号整数。这些宏可用于来回转换 SM 代表符号 + 幅度，ULL 代表无符号 long long (uint64_t)。假设双精度数被强制转换为 unsigned long long 类型以便使用这些宏：

#define SM2ULL(x) ((x)^(((~(x) >> 63)-1) | 0x8000000000000000ull))
#define ULL2SM(x) ((x)^((( (x) >> 63)-1) | 0x8000000000000000ull))

请注意，使用这些宏会将负零视为小于正零，但这通常不是问题。

由于基数排序需要初始读取传递来生成计数矩阵（然后将其转换为逻辑桶边界的起始或结束索引），因此在这种情况下，初始读取传递将是复制传递，它也会生成计数矩阵。基于 256 的排序将使用大小为 [8][256] 的矩阵，并且在复制之后，将执行 8 次基数排序。如果向量远大于缓存大小，则主要时间因素将是每个基数排序过程中的随机访问写入。

Answer 3

中有std::partial_sort_copy()