gpt4 book ai didi

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

转载 作者:太空狗 更新时间:2023-10-29 20:39:38 25 4
gpt4 key购买 nike

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

最佳答案

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 已按照您想要的方式排序。

关于c++ - 如何以稳定的方式进行部分排序,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/27247828/

25 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com