Sorted Vector of Double Precision Reals 对一组双精度实数进行排序并获得它们的排序向量

Question

Sorted Vector of Double Precision Reals 对一组双精度实数进行排序并获得它们的排序向量

6

在C++中，我想对一个长达（2^20）的实数向量进行排序，很明显可以使用sort()函数来完成。之前我使用过R语言，习惯于使用方便的order()函数，该函数返回导致有序向量的排列顺序。

示例：

x = {24, 55, 22, 1}

然后是排列。

perm = {3, 2, 0, 1}

将原始的x映射到按升序排序的x。

我可能可以实现一些冒泡排序，不仅可以对x进行排序，还可以在向量{0,1,2,...}上执行相同的置换并输出两者，但我相信有人一定考虑过它，特别是有效地完成了它。

- Philipp

3个回答

4

您可以使用std::sort对二元组列表{(24, 0), (55, 2), (22, 0), (1, 1)}进行排序。虽然不太美观，但我通常会这样做：

#include <vector>
#include <algorithm>
#include <utility>

typedef std::pair<double, int> Pair;

struct CmpPair
{
    bool operator()(const Pair& a, const Pair& b)
    { return a.first < b.first; }
};

void sortingPermutation(
    const std::vector<double>& values,
    std::vector<int>& permutation)
{
    std::vector<Pair> pairs;
    for (int i = 0; i < (int)values.size(); i++)
        pairs.push_back(Pair(values[i], i));

    std::sort(pairs.begin(), pairs.end(), CmpPair());

    typedef std::vector<Pair>::const_iterator I;
    for (I p = pairs.begin(); p != pairs.end(); ++p)
        permutation.push_back(p->second);
}

这里是测试：

#include <iostream>

int main()
{
    std::vector<double> values;
    values.push_back(24);
    values.push_back(55);
    values.push_back(22);
    values.push_back(1);

    std::vector<int> permutation;
    sortingPermutation(values, permutation);

    typedef std::vector<int>::const_iterator I;
    for (I p = permutation.begin(); p != permutation.end(); ++p)
        std::cout << *p << " ";
    std::cout << "\n";
}

- antonakos

1

做得好。此外，将其制作为一个模板以便能够对不仅仅是双精度数进行排序将会非常棒。当然，在向向量调用reserve时，通过减少对new/malloc的调用次数，可以节省大量时间。 - user405725

3

编辑

不使用辅助向量的更好方法：（ideone 上的源代码）：

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

template<class Vals>
void sortingPermutation(const Vals& values, std::vector<int>& v){
  int size = values.size(); 
  v.clear(); v.reserve(size);
  for(int i=0; i < size; ++i)
    v.push_back(i);

  std::sort(v.begin(), v.end(), [&values](int a, int b) -> bool { 
    return values[a] < values[b];
  });
}

int main()
{
    std::vector<double> values;
    values.push_back(24);
    values.push_back(55);
    values.push_back(22);
    values.push_back(1);

    std::vector<int> permutation;
    sortingPermutation(values, permutation);

    typedef std::vector<int>::const_iterator I;
    for (I p = permutation.begin(); p != permutation.end(); ++p)
        std::cout << *p << " ";
    std::cout << "\n";
}

我正在使用C++0x中的lambda表达式，但是它可以被简单的函数对象所替代:

template<class T>
struct CmpPairs{
  CmpPairs(const std::vector<T> &v): v_(v) {}
  std::vector<T> v_;
  bool operator()(int a, int b){ return v_[a] < v_[b]; }
};

template<class T>
CmpPairs<T> CreateCmpPairs(const std::vector<T> & v) { return CmpPairs<T>(v); }
//in sortingPermutation:
std::sort(v.begin(), v.end(), CreateCmpPairs(values));

旧解决方案的来源是使用std::map： ideone

- Pawel Zubrycki

1

我看到的经验法则是，对向量进行排序比使用自排序容器更有效。从未测试过它的真实性。 - Mark Ransom

更好的方法是使用C++0x（可以用函数对象替换lambda）：http://www.ideone.com/wRHYv 我认为比antonakos的方法要好得多，因为没有辅助对象来进行排序。 - Pawel Zubrycki

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Chris Dodd · Accepted Answer

我认为最好的方法是创建一个整数向量0..N，然后使用比较函数对该数组进行排序，该比较函数将比较您试图找到排序置换的向量的相应元素。类似于：

#include <vector>
#include <algorithm>

template<class T> class sorter {
    const std::vector<T> &values;
public:
    sorter(const std::vector<T> &v) : values(v) {}
    bool operator()(int a, int b) { return values[a] < values[b]; }
};

template<class T> std::vector<int> order(const std::vector<T> &values)
{
    std::vector<int> rv(values.size());
    int idx = 0;
    for (std::vector<int>::iterator i = rv.begin(); i != rv.end(); i++)
        *i = idx++;
    std::sort(rv.begin(), rv.end(), sorter<T>(values));
    return rv;
}

这样可以最小化分配开销，因为我们不会创建任何大型临时对象进行排序，然后提取最终的排列 -- 被返回的同一向量是用于排序的临时变量。