如何在排序后获得索引排列

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

这是关于ideone的演示.

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

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

Answer 2

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

对于不稳定的算法,这会将其更改为稳定的算法.

但请注意,如果您尝试以这种方式进行排序,则会在排序时生成索引,而不是在排序后

此外,由于知道置换索引会导致O(n)排序算法,因此您不能比O(nlogn)更快地完成它.