c ++比较器使用辅助数组进行排序

Question

我有一个无法修改的数组（比如 values）。我想知道这个数组中的值是否已排序，最终的 position/index 是什么。因此，为此我只是使用如下代码：

#include <iostream>
#include <algorithm>
#include <vector>
#include <numeric>

int main() {
    std::vector<unsigned> position(11, 0);
    std::iota(position.begin(), position.end(), 0);
    std::vector<unsigned> values = {140, 141, 118, 119, 122, 123, 128, 129, 133, 134, 138, 139};
    
    auto value_comparator = [&values](const unsigned& index1, const unsigned& index2) {
        return (values[index1] < values[index2]);
    };
    
    std::sort(position.begin(), position.end(), value_comparator);
    
    for (auto val : position) {
        std::cout << val << " ";
    }
    std::cout << std::endl;

    return 0;
}

实际输出:

2 3 4 5 6 7 8 9 10 0 1

预期输出：

10 11 0 1 2 3 4 5 6 7 8 9

我试图理解为什么输出如上所示。看起来 STL 使用 IntroSort。在我深入挖掘之前寻找一些输入。

谢谢。

Answer 1

您的代码根据数组中的值对索引进行排序。所以输出的第一个位置是最小值的索引，第二个是 second-smallest 的索引，依此类推。

要从中得到你想要的，例如，你可以执行以下操作：

std::vector<unsigned> result(position.size());
for(unsigned i = 0; i < position.size(); ++i) {
    result[position[i]] = i;
}

c ++比较器使用辅助数组进行排序

c++ comparator sorting using auxillary array

c++

sorting

lambda

stl