排序后如何获取索引排列

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 的最小元素。

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

原文由 q0987 发布，翻译遵循 CC BY-SA 4.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

这是 关于 ideone 的演示。

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

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

原文由 Sergey Kalinichenko 发布，翻译遵循 CC BY-SA 3.0 许可协议

Answer 2

为什么不放一些卫星数据？无需对数字进行排序，只需对成对的数字及其索引进行排序。由于排序首先在该对的第一个元素上完成，因此这不应破坏稳定的排序算法。

对于不稳定的算法，这会将其更改为稳定的算法。

但请注意，如果您尝试以这种方式排序，它会在排序时生成索引，而不是在排序之后。

此外，由于知道排列索引会导致 O(n) 排序算法，所以你不能比 O(nlogn) 更快地做到这一点。

原文由 zw324 发布，翻译遵循 CC BY-SA 3.0 许可协议