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

Question

是std::partial_sort稳定的,如果没有,是否有标准库提供的稳定局部排序或例如boost？

Answer 1

partial_sort是有效且易于提供的,因为它基本上是一个快速排序,其中跳过了对于期望范围不必要的递归.没有等效的有效部分稳定排序算法; stable_sort通常实现为合并排序,并且合并排序的递归以错误的方式工作.

如果要使局部排序稳定,则需要将位置信息与每个元素相关联.如果你有一个可修改的zip范围你可以通过将元素和iota向量压缩在一起来实现,但是在当前的迭代器概念中实际上不可能构建可修改的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;
  });

现在你的基矢量仍未排序,但迭代器矢量按你想要的方式排序.