C++是否有类似std::partial_sort的内置函数可返回排序值位置？

C++标准库中没有直接返回目标位置的内置函数，但可以通过结合现有算法快速实现需求，以下是两种常用方案：

方案一：使用std::partial_sort_copy获取有序的位置列表 #

这种方法会得到有序的最小/最大M个位置，时间复杂度为O(N log M)，适合需要有序结果的场景。

步骤：

1. 创建一个包含所有元素索引的容器，用std::iota初始化索引值。
2. 用std::partial_sort_copy根据原列表的元素值对索引进行排序，取前M个索引。

示例代码（找最小的M个值的位置）：

#include <vector>
#include <algorithm>
#include <numeric>

int main() {
    std::vector<int> nums = {5, 2, 9, 1, 5, 6};
    const int M = 3; // 目标数量

    std::vector<int> indices(nums.size());
    std::iota(indices.begin(), indices.end(), 0); // 初始化索引为0,1,2,...n-1

    // 按原数组元素升序排序索引，仅保留前M个有序的最小元素索引
    std::partial_sort_copy(indices.begin(), indices.end(),
                           indices.begin(), indices.begin() + M,
                           [&nums](int a, int b) { return nums[a] < nums[b]; });

    // 此时indices的前M个元素就是最小M个值的位置（0-based）
    for (int i = 0; i < M; ++i) {
        // 输出或处理这些位置
    }
    return 0;
}

如果要找最大的M个值的位置，只需将比较函数修改为nums[a] > nums[b]即可。

方案二：使用std::nth_element获取高性能的位置列表 #

这种方法时间复杂度为O(N)，适合大数据量场景，缺点是前M个位置默认是无序的，如果需要有序可以额外对前M个索引排序。

步骤：

1. 同样初始化索引容器。
2. 用std::nth_element将第M小（或大）的索引放到正确位置，其左侧的所有索引对应的值都小于（或大于）该位置的值。

示例代码（找最小的M个值的位置）：

#include <vector>
#include <algorithm>
#include <numeric>

int main() {
    std::vector<int> nums = {5, 2, 9, 1, 5, 6};
    const int M = 3;

    std::vector<int> indices(nums.size());
    std::iota(indices.begin(), indices.end(), 0);

    // 将第M小的索引放到位置M-1，左侧均为更小的元素的索引
    std::nth_element(indices.begin(), indices.begin() + M, indices.end(),
                     [&nums](int a, int b) { return nums[a] < nums[b]; });

    // 若需要有序的位置列表，可对前M个索引排序
    std::sort(indices.begin(), indices.begin() + M);

    // 前M个元素即为目标位置
    return 0;
}

注意事项 #

• 当列表存在重复元素时，两种方法都会保留所有对应位置，符合需求。
• 所有操作仅针对索引容器，不会修改原列表的元素顺序。

内容的提问来源于stack exchange，提问作者unknown