部分位逆序排序逆算法需求：从逆序结果恢复原排列

原算法通过计算每个索引的低levels位逆序值，对数组进行稳定排序，实现仅考虑最低n位的稳定位逆序排序。现在需要实现逆算法，从排序后的数组恢复原始排列。

逆算法思路 #

原算法的核心逻辑是：

• 为每个原始索引i计算低levels位的逆序值rev_i
• 将<rev_i, 元素值>按rev_i升序稳定排序（同rev_i的元素保留原始索引的顺序）

逆过程需要反向映射：

1. 预先生成所有原始索引i对应的rev_i，并按rev_i分组，每组内保留原始索引的升序（和原算法排序时的同组顺序一致）
2. 遍历排序后的数组，按rev_i的分组顺序，将元素依次放回对应分组的原始索引位置
3. 最终得到恢复后的原始数组

逆算法代码实现 #

#include <vector>
#include <algorithm>
#include <map>

// 复用原有的位逆序索引计算函数
auto bit_reversed_index(int index, uint8_t levels) -> int
{
    int rev = 0;
    for (int i = 0; i < levels; ++i) {
        rev <<= 1;
        rev |= (index & 1);
        index >>= 1;
    }
    return rev;
}

// 逆算法：从部分位逆序后的数组恢复原始数组
auto reverse_partial_bit_reverse(std::vector<double>& sorted_signal, size_t n, uint8_t levels) -> void
{
    // 按rev值分组，存储对应的原始索引（保持原始索引升序）
    std::map<int, std::vector<int>> rev_to_indices;
    for (size_t i = 0; i < n; ++i) {
        int rev = bit_reversed_index(static_cast<int>(i), levels);
        rev_to_indices[rev].push_back(static_cast<int>(i));
    }

    // 遍历排序后的数组，按分组依次放回原始索引位置
    std::vector<double> original(n);
    size_t sorted_idx = 0;
    for (const auto& [rev, indices] : rev_to_indices) {
        for (int orig_idx : indices) {
            original[orig_idx] = sorted_signal[sorted_idx++];
        }
    }

    // 将恢复后的原始数组拷贝回输入
    sorted_signal.swap(original);
}

验证示例 #

示例1：levels=1 #

排序后数组：1 3 5 7 2 4 6 8
逆算法恢复后：1 2 3 4 5 6 7 8

示例2：levels=2 #

排序后数组：1 5 3 7 2 6 4 8
逆算法恢复后：1 2 3 4 5 6 7 8

代码说明 #

• 复用原有的bit_reversed_index函数保证索引计算的一致性
• 使用std::map自动按rev值升序排列分组，和原算法的排序顺序匹配
• 同rev分组内的原始索引保持升序，对应原算法稳定排序后的同组元素顺序
• 通过临时数组original存储恢复后的结果，避免覆盖输入数据

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