C++ vector降序排序：未排序元素到排序后位置的高效映射方法

你当前基于std::find的实现不是最高效方案，时间复杂度为O(n²)，处理大规模向量时性能损耗极大，同时无法正确处理重复元素场景。存在O(n log n)时间复杂度的最优实现，逻辑简洁且完全满足顺序要求。

• 输入：未排序的std::vector<float>
• 输出1：原向量的降序排序结果
• 输出2：正向索引映射数组，满足map[i] = 原向量第i个元素在排序后数组中的位置
• 顺序约束：原数组中位置靠前的相等元素，在排序后数组中也占据更靠前的位置，避免索引错位

初始向量：v = {4.5, 1.2, 3.4, 2.3}
降序排序后向量：v_s = {4.5, 3.4, 2.3, 1.2}
符合要求的映射结果：map = {0, 3, 1, 2}
不符合要求的错误结果：map = {0, 2, 3, 1}

1. 性能问题：对原数组的每个元素，都通过std::find遍历整个排序后数组查找位置，整体时间复杂度为O(n²)，当向量规模达到十万、百万级时，耗时会呈平方级增长，完全不适合高频、大数据量场景。
2. 正确性问题：当数组中存在相等元素时，std::find永远返回第一个匹配值的位置，会导致相等元素的索引映射完全错乱，无法满足顺序要求。

核心思路是先构建反向索引（排序后位置 -> 原数组位置，这部分你已经了解实现方式），再通过一次O(n)的遍历直接填充正向映射，整体时间复杂度和排序操作一致，为O(n log n)，是该问题的理论最优复杂度。

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

template <typename T>
std::vector<size_t> get_forward_sort_map(const std::vector<T>& v_unsorted, std::vector<T>& v_sorted) {
    const size_t elem_count = v_unsorted.size();
    // 初始化反向索引数组，初始值为0,1,2...elem_count-1，对应原数组下标
    std::vector<size_t> reverse_idx(elem_count);
    std::iota(reverse_idx.begin(), reverse_idx.end(), 0);

    // 对反向索引排序：按原数组值降序排列，值相等时原下标更小的排前面，保证顺序稳定
    std::sort(reverse_idx.begin(), reverse_idx.end(), [&](size_t a, size_t b) {
        if (v_unsorted[a] != v_unsorted[b]) {
            return v_unsorted[a] > v_unsorted[b];
        }
        return a < b;
    });

    // 填充排序后数组（如果不需要排序后结果可以删掉这部分）
    v_sorted.resize(elem_count);
    for (size_t sorted_pos = 0; sorted_pos < elem_count; ++sorted_pos) {
        v_sorted[sorted_pos] = v_unsorted[reverse_idx[sorted_pos]];
    }

    // 一次遍历填充正向映射，时间复杂度O(n)
    std::vector<size_t> forward_map(elem_count);
    for (size_t sorted_pos = 0; sorted_pos < elem_count; ++sorted_pos) {
        size_t original_pos = reverse_idx[sorted_pos];
        forward_map[original_pos] = sorted_pos;
    }

    return forward_map;
}

实现说明 #

• 性能表现：除了排序操作本身的O(n log n)开销外，其余操作都是线性时间复杂度，没有额外性能损耗，完全满足高频、大规模向量的处理需求。
• 正确性保证：排序比较逻辑中加入了相等元素的下标判断，实现了稳定排序效果，不会出现相等元素索引错位的问题。
• 空间开销：仅额外使用两个长度为n的size_t类型数组，内存开销极低。
• 灵活性：如果不需要单独输出排序后的数组，直接删除对应填充v_sorted的代码段即可，性能还可进一步提升。

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