c++ - 如何以稳定的方式进行部分排序

Question

std::partial_sort 是否稳定，如果不是，是否有标准库提供的稳定的部分排序，或者例如提振？

Answer 1

partial_sort 高效且易于提供，因为它基本上是一种快速排序，其中跳过了所需范围不需要的递归。不存在等效高效的部分稳定排序算法； stable_sort 通常实现为归并排序，而归并排序的递归工作方式不对。

如果想让偏排序稳定，就需要给每个元素关联位置信息。如果你有一个可修改的 zip 范围，你可以通过将元素和 iota vector 压缩在一起来实现，但可修改的 zip 范围实际上不可能在当前的迭代器概念中构建，因此通过迭代器进行间接排序并依赖迭代器更容易'订购。换句话说，您可以这样做:

using MyThingV = std::vector<MyThing>;
using MyThingIt = typename MyThingV::iterator;
MyThingV things;
// Set up a vector of iterators. We'll sort that.
std::vector<MyThingIt> sorted; sorted.reserve(things.size());
for (auto it = things.begin(); it != things.end(); ++it) sorted.push_back(it);

std::partial_sort(sorted.begin(), sorted.begin() + upto_index, sorted.end(),
  [](MyThingIt lhs, MyThingIt rhs) {
    // First see if the underlying elements differ.
    if (*lhs < *rhs) return true;
    if (*rhs < *lhs) return false;
    // Underlying elements are the same, so compare iterators; these represent
    // position in original vector.
    return lhs < rhs;
  });

现在您的基本 vector 仍未排序，但迭代器 vector 已按照您想要的方式排序。