c++ - std::sort 是对整数值有限的巨大数组进行就地排序的最佳选择吗？

Question

我想对一个包含大量(数百万甚至数十亿)元素的数组进行排序，而值是小范围内的整数(1 到 100 或 1 到 1000)，在这种情况下，是 std::sort 和并行化版本 __gnu_parallel::sort 是我的最佳选择？

实际上我想用一个代表处理器索引的整数成员对我自己的类的 vector 进行排序。

由于类中还有其他成员，因此，即使两个数据具有相同的用于比较的整数成员，也可能不会将它们视为相同的数据。

Answer 1

如果您知道您的范围如此有限，那么计数排序将是正确的选择。如果范围是 [0,m) 最有效的方法是它有一个 vector，其中索引代表元素，值代表计数。例如:

vector<int> to_sort;
vector<int> counts;
for (int i : to_sort) {
  if (counts.size() < i) {
    counts.resize(i+1, 0);
  }
  counts[i]++;
}

请注意，i 处的计数是延迟初始化的，但如果您知道 m，则可以调整一次大小。

如果您按某个字段对对象进行排序并且它们都是不同的，则可以将上面的内容修改为:

vector<T> to_sort;
vector<vector<const T*>> count_sorted;
for (const T& t : to_sort) {
  const int i = t.sort_field()
  if (count_sorted.size() < i) {
    count_sorted.resize(i+1, {});
  }
  count_sorted[i].push_back(&t);
}

现在的主要区别在于您的空间需求大幅增长，因为您需要存储指针 vector 。空间复杂度从 O(m) 变为 O(n)。时间复杂度是一样的。请注意，该算法是稳定的。上面的代码假定 to_sort 在 count_sorted 的生命周期内处于范围内。如果您的 T 实现了移动语义，您可以存储对象本身并将它们移入。如果您需要 count_sorted 比 to_sort 更有效，您将需要这样做或复制。

如果你有一个 [-l, m) 类型的范围，内容不会有太大变化，但你的索引现在代表值 i + l 而你需要事先知道l。

最后，通过迭代 counts 数组并考虑计数值来模拟排序数组的迭代应该是微不足道的。如果您想要 STL 之类的迭代器，您可能需要一个封装该行为的自定义数据结构。

注意:在此回答的前一个版本中，我提到了 multiset 作为一种使用数据结构进行计数排序的方法。这在一些 java 实现中是有效的(我相信 Guava 实现是有效的)但在 C++ 中不是，因为 RB 树中的键只是重复了很多次。