c++ - 排序后如何获取索引排列

Question

给定一个数组arr = {5, 16, 4, 7}，我们可以通过sort(arr, arr+sizeof(arr)/sizeof(arr[0] ))。 所以现在数组 arr = {4, 5, 7, 16} 和排序数组的排列索引是 {2, 0, 3, 1}。 换句话说，原始数组中的 arr[2] 现在是排序数组中位置 0 的最小元素。

有没有一种有效的方法可以让我们得到排列索引？

Answer 1

创建一个索引数组，用数字 0..N-1 填充它，然后使用自定义比较器对其进行排序。比较器应该比较原始数组中索引 lhs 和 rhs 处的项目。以这种方式对索引数组进行排序会将它们重新排序为排列:

vector<int> data = {5, 16, 4, 7};   
vector<int> index(data.size(), 0);
for (int i = 0 ; i != index.size() ; i++) {
    index[i] = i;
}
sort(index.begin(), index.end(),
    [&](const int& a, const int& b) {
        return (data[a] < data[b]);
    }
);
for (int i = 0 ; i != index.size() ; i++) {
    cout << index[i] << endl;
}

这会打印出 2, 0, 3, 1

这里是 demo on ideone .

注意:您可以使用 index 来按排序顺序检索 data:

for (int i = 0 ; i != index.size() ; i++) {
    cout << data[index[i]] << endl;
}