使用c++(最好是标准库)，我想对一个样本序列进行升序排序，但我也想记住新样本的原始索引。
例如，我有一个集合，或向量，或样本a的矩阵:[5,2,1,4,3]。我想把它们排序为B:[1,2,3,4,5]，但我也想记住这些值的原始索引，所以我可以得到另一个集合，它将是: C:[2,1,4,3,0] -这对应于'B'中每个元素的索引，在原始'A'中。
例如，在Matlab中，你可以这样做:
[a,b]=sort([5, 8, 7])
a = 5 7 8
b = 1 3 2
有谁能想到一个好办法吗?
当前回答
假设给定向量为
A=[2,4,3]
创建一个新向量
V=[0,1,2] // indicating positions
对V进行排序，而不是比较V中的元素，比较A中对应的元素
//Assume A is a given vector with N elements
vector<int> V(N);
std::iota(V.begin(),V.end(),0); //Initializing
sort( V.begin(),V.end(), [&](int i,int j){return A[i]<A[j];} );
其他回答
假设给定向量为
A=[2,4,3]
创建一个新向量
V=[0,1,2] // indicating positions
对V进行排序，而不是比较V中的元素，比较A中对应的元素
//Assume A is a given vector with N elements
vector<int> V(N);
std::iota(V.begin(),V.end(),0); //Initializing
sort( V.begin(),V.end(), [&](int i,int j){return A[i]<A[j];} );
我的解法使用了余数法。我们可以把需要排序的值放在上面2个字节，而把元素的下标放在下面2个字节:
int myints[] = {32,71,12,45,26,80,53,33};
for (int i = 0; i < 8; i++)
myints[i] = myints[i]*(1 << 16) + i;
然后像往常一样对数组myint进行排序:
std::vector<int> myvector(myints, myints+8);
sort(myvector.begin(), myvector.begin()+8, std::less<int>());
在此之后，您可以通过渣滓访问元素的指数。下面的代码输出按升序排序的值的索引:
for (std::vector<int>::iterator it = myvector.begin(); it != myvector.end(); ++it)
std::cout << ' ' << (*it)%(1 << 16);
当然，这种技术只适用于原始数组myint中相对较小的值(即可以装入int的前2个字节的值)。但是它还有一个额外的好处，可以区分相同的myint值:它们的下标将按正确的顺序打印。
考虑使用@Ulrich Eckhardt建议的std::multimap。只是代码可以变得更简单。
鉴于
std::vector<int> a = {5, 2, 1, 4, 3}; // a: 5 2 1 4 3
在插入的平均时间内排序
std::multimap<int, std::size_t> mm;
for (std::size_t i = 0; i != a.size(); ++i)
mm.insert({a[i], i});
检索值和原始索引
std::vector<int> b;
std::vector<std::size_t> c;
for (const auto & kv : mm) {
b.push_back(kv.first); // b: 1 2 3 4 5
c.push_back(kv.second); // c: 2 1 4 3 0
}
首选std::multimap而不是std::map的原因是允许原始向量的值相等。另外请注意，与std::map不同，操作符[]没有为std::multimap定义。
向量中的项是唯一的吗?如果是这样，复制向量，排序一个副本与STL排序，然后你可以找到每个项目在原始向量的索引。
如果向量应该处理重复的项，我认为你最好实现自己的排序例程。
vector<pair<int,int> >a;
for (i = 0 ;i < n ; i++) {
// filling the original array
cin >> k;
a.push_back (make_pair (k,i)); // k = value, i = original index
}
sort (a.begin(),a.end());
for (i = 0 ; i < n ; i++){
cout << a[i].first << " " << a[i].second << "\n";
}
现在a包含了我们的值和它们在排序中的下标。
[我]。First =第i条的值。
[我]。Second =初始数组中的idx。
