我有一个看似很基本的问题，但这是在“每个CPU滴答声都非常重要”的情况下（这是将在超级计算机上使用的较大算法的一部分。
问题很简单：对无符号long long int数字及其原始索引进行排序的最快方法是什么？ （开始时，无符号long long int数是完全随机的顺序。）
Example :
Before
Numbers: 32 91 11 72
Indexes: 0 1 2 3
After
Numbers: 11 32 72 91
Indexes: 2 0 3 1
通过“最快的方式”，我的意思是：使用哪种算法：std :: sort，C qsort或网络上可用的其他排序算法？使用什么容器（C数组，std :: vector，std :: map ...）？如何同时对索引排序（使用结构，std :: pair，std :: map ...）？
要排序多少个元素？ ->通常为4Go]
明显的起点是为它定义了operator<的结构：
struct data {
unsigned long long int number;
size_t index;
};
struct by_number {
bool operator()(data const &left, data const &right) {
return left.number < right.number;
}
};
...和用于保存数据的std :: vector：
std::vector<data> items;
和std::sort进行排序：
std::sort(items.begin(), items.end(), by_number());
简单的事实是，普通容器（等等）足够高效，因此使用它们不会使您的代码效率大大降低。您might可以通过用不同的方式编写某些部分来做得更好，但是您可能同样容易做得更糟。从扎实且易读的内容开始，然后进行测试-不要（试图）过早地进行优化。
编辑：当然，在C ++ 11中，您可以改用lambda表达式：
std::sort(items.begin(), items.end(),
[](data const &a, data const &b) { return a.number < b.number; });
这通常更方便编写。可读性取决于-对于这样的简单事情，我想说sort ... by_number可读性很强，但这（很大程度上）取决于您给比较运算符提供的名称。 lambda使实际的排序标准更容易找到，因此您无需仔细选择名称即可读取代码。
std::pair和std::sort完全符合您的要求：如果将值放入pair.first和pair.second中的索引，则可以简单地在sort s的向量上调用pair，例如这个：
// This is your original data. It does not need to be in a vector
vector<long> orig;
orig.push_back(10);
orig.push_back(3);
orig.push_back(6);
orig.push_back(11);
orig.push_back(2);
orig.push_back(19);
orig.push_back(7);
// This is a vector of {value,index} pairs
vector<pair<long,size_t> > vp;
vp.reserve(orig.size());
for (size_t i = 0 ; i != orig.size() ; i++) {
vp.push_back(make_pair(orig[i], i));
}
// Sorting will put lower values ahead of larger ones,
// resolving ties using the original index
sort(vp.begin(), vp.end());
for (size_t i = 0 ; i != vp.size() ; i++) {
cout << vp[i].first << " " << vp[i].second << endl;
}
std::sort被证明比旧的qsort快，因为缺乏间接性，并且可以内嵌关键操作。
std::sort的实现可能已高度优化且难以超越，但并非没有可能。如果数据是固定长度且较短，则可能会发现Radix sort更快。 Timsort相对较新，并且为Python提供了良好的效果。
您可能将索引数组与值数组分开，但是我认为间接的额外级别将被证明是速度杀手。最好将它们放在一个结构或std::pair中。
与任何对速度有严格要求的应用程序一样，您必须尝试一些实际的实现，并进行比较以确保最快。
它[[可能
struct SomeValue
{
unsigned long long val;
size_t index;
bool operator<(const SomeValue& rhs)const
{
return val < rhs.val;
}
}
#include <algorithm>
std::vector<SomeValue> somevec;
//fill it...
std::sort(somevec.begin(),somevec.end());
std::vector和std::sort。那应该提供最快的排序方法。要查找原始索引，请创建一个结构。