使用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];} );

其他回答

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。

我最近接触了c++ 20 <ranges>的优雅投影特性,它允许编写更短/更清晰的代码:

std::vector<std::size_t> B(std::size(A));
std::iota(begin(B), end(B), 0);
std::ranges::sort(B, {}, [&](std::size_t i){ return A[i]; }); 

{}指通常的std::less<std::size_t>。因此,正如您所看到的,我们定义了一个函数,在任何比较之前调用每个元素。这个投影特性实际上是非常强大的,因为这个函数可以是,就像这里,或者它甚至可以是一个方法,或者一个成员值。例如:

struct Item {
    float price;
    float weight;
    float efficiency() const { return price / weight; }
};

int main() {
    std::vector<Item> items{{7, 9}, {3, 4}, {5, 3}, {9, 7}};
    std::ranges::sort(items, std::greater<>(), &Item::efficiency);
    // now items are sorted by their efficiency in decreasing order:
    // items = {{5, 3}, {9, 7}, {7, 9}, {3, 4}}
}

如果我们想通过增加价格来排序:

std::ranges::sort(items, {}, &Item::price);

不要定义操作符<或使用lambda,使用投影!

使用c++ 11 lambdas:

#include <iostream>
#include <vector>
#include <numeric>      // std::iota
#include <algorithm>    // std::sort, std::stable_sort

using namespace std;

template <typename T>
vector<size_t> sort_indexes(const vector<T> &v) {

  // initialize original index locations
  vector<size_t> idx(v.size());
  iota(idx.begin(), idx.end(), 0);

  // sort indexes based on comparing values in v
  // using std::stable_sort instead of std::sort
  // to avoid unnecessary index re-orderings
  // when v contains elements of equal values 
  stable_sort(idx.begin(), idx.end(),
       [&v](size_t i1, size_t i2) {return v[i1] < v[i2];});

  return idx;
}

现在您可以在迭代中使用返回的索引向量,例如

for (auto i: sort_indexes(v)) {
  cout << v[i] << endl;
}

您还可以选择提供原始索引向量、排序函数、比较器,或者使用额外的向量在sort_indexes函数中自动重新排序v。

我的解法使用了余数法。我们可以把需要排序的值放在上面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值:它们的下标将按正确的顺序打印。

向量中的项是唯一的吗?如果是这样,复制向量,排序一个副本与STL排序,然后你可以找到每个项目在原始向量的索引。

如果向量应该处理重复的项,我认为你最好实现自己的排序例程。