对数组进行升序排序时如何存储原数组的原始索引

需求为对array_dist数组升序排序，同时生成存储原数组对应位置的index_arr数组。例如原数组[5,4,3,2,1]排序后为[1,2,3,4,5]，对应的索引数组为[4,3,2,1,0]。

你手写的交换逻辑本身是正确的，只要交换array_dist元素的同时同步交换index_arr的对应元素，就能保证索引和值的对应关系。但手动实现的O(n²)排序逻辑在数组长度为4344的场景下效率极低，更推荐使用标准库的排序方案，可选两种实现方式：

方案1：单独排序索引数组（无需修改原array_dist结构） #

如果你的array_dist是单纯的float数组，不需要修改原结构，直接对索引数组排序即可：

#include <vector>
#include <algorithm>

// 初始化索引数组
std::vector<int> index_arr(4344);
for (int i = 0; i < 4344; ++i) {
    index_arr[i] = i;
}

// 按array_dist的值升序排列索引
std::sort(index_arr.begin(), index_arr.end(), [&](int a, int b) {
    return array_dist[a] < array_dist[b];
});

// 如果需要同步得到排序后的数值数组
std::vector<float> sorted_dist(4344);
for (int i = 0; i < 4344; ++i) {
    sorted_dist[i] = array_dist[index_arr[i]];
}

// 输出结果
std::cout << "print out distance column after ascending sorting : \n";
for (int i = 0; i < 4344; ++i) {
    std::cout << index_arr[i] << " : " << sorted_dist[i] << std::endl;
}

方案2：索引值绑定排序（和你提供的参考代码逻辑一致） #

把索引和对应的值绑定为pair，直接对pair数组排序：

#include <vector>
#include <algorithm>
#include <utility>

// 构造索引+值的pair数组
std::vector<std::pair<int, float>> array_dist_pair(4344);
for (int i = 0; i < 4344; ++i) {
    array_dist_pair[i] = {i, array_dist[i]};
}

// 按值升序排序
std::sort(array_dist_pair.begin(), array_dist_pair.end(), [](const std::pair<int, float>& s1, const std::pair<int, float>& s2) {
    return s1.second < s2.second;
});

// 输出结果
std::cout << "print out distance column after ascending sorting : \n";
for (int i = 0; i < 4344; ++i) {
    std::cout << array_dist_pair[i].first << " : " << array_dist_pair[i].second << std::endl;
}

如果坚持使用手写排序逻辑，确认以下两点即可正常运行：

• array_dist是长度为4344的float数组，排序前没有被修改
• 不存在数组越界访问的问题

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