高效地对定义排序的向量子集进行排序

Question

我有一个向量，它定义了项目的顺序（0..N-1），例如：{5, 0, 4, 3, 2, 1, 7, 6}。

我需要对该向量的子集进行排序。因此，对于{0，1，2，5}，我应该得到{5，0，2，1}。

我尝试了以下解决方案：

1. 在子集中创建项目集，然后清除子集，在排序向量中遍历，仅添加集合中的项目。
2. 通过在排序向量中遍历，仅添加通过std::lower_bound找到的子集中的项目，从而创建新的已排序向量。

第二种解决方案似乎更快，尽管它需要对子集进行排序。是否有更好的解决方案？我使用C++ / STL / Qt，但问题可能与语言无关。

- Michal

---

如果您需要对许多小子集进行排序，建议创建一个向量来表示每个项目的位置：{1,5,4,3,2,0,7,6}。然后，您可以使用比较函数在该向量中查找，并调用std::sort进行排序。请注意，此方法可以提高排序效率。 - Marc Glisse

Marc的建议示例 。（顺便说一句，Marc，您应该考虑将其作为一个可行的答案发布）。 - WhozCraig

@Michal，从依赖于N和n的复杂度转变为仅依赖于n的复杂度，对我来说已经是一个巨大的胜利了...如果这还不够好，你可以用基数排序或任何专门针对小整数的其他排序方法替换std::sort，主要的问题是你可以忘记排序向量，使用查找表将问题简化为常规排序，这方面有丰富的文献资料。 - Marc Glisse

我想接受Marc的答案，但他将其添加为评论。有没有办法将其移动到答案中？ - Michal

@Michal 当你成功解决问题后，可以写下自己的答案来解释如何修复它。如果有人的评论帮助到了你，给他们点个赞（在任何地方提到他们的名字，不要忘记代码示例中的WhozCraig）。将答案用原作者的话表述可能会使通过谷歌找到它的人更容易使用/访问。 - Marc Glisse

Answer 1

请查看以下代码：

#include <iostream>
#include <algorithm>
#include <vector>


    struct cmp_subset
    {
        std::vector<int> vorder;

        cmp_subset(const std::vector<int>& order)
        {
            vorder.resize(order.size());
            for (int i=0; i<order.size(); ++i)
                vorder.at(order[i]) = i;
        }

        bool operator()(int lhs, int rhs) const
        {
            return vorder[lhs] < vorder[rhs];
        }
    };

    int main()
    {
        std::vector<int> order = {5, 0, 4, 3, 2, 1, 7, 6};
        std::vector<int> subset = {0, 1, 2, 5};

        for (auto x : subset)
            std::cout << x << ' ';
        std::cout << '\n';

        std::sort(subset.begin(), subset.end(), cmp_subset(order));

        for (auto x : subset)
            std::cout << x << ' ';
        std::cout << '\n';

        return 0;
    }

这段代码从这里复制而来。

- Naseef Chowdhury

---

这个解决方案最早是在评论区被Marc Glisse提出的。 - Michal