我有一个看起来很基本的问题，但它是在一个“每一个CPU滴答计数”（这是将在超级计算机上使用的更大算法的一部分）的上下文中提出的。
问题很简单:对一个由无符号长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，还是web上可用的另一种排序算法？要使用的容器（C数组，std::Vector，std::Map...)？如何同时对索引进行排序（使用结构，std::pair，std::map...)？
要排序多少元素？-&>；通常是4GO的数字
显而易见的起点是定义了
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(items.begin(), items.end(), by_number());
简单的事实是，普通的容器（以及类似的容器）足够有效，使用它们并不会使代码的效率大大降低。你也许可以通过用不同的方式写一些部分来做得更好，但你也可能很容易做得更差。从可靠的，可读的开始，并进行测试--不要（试图）过早地优化。
编辑:当然，在C++11中，您可以使用lambda表达式来代替:
std::sort(items.begin(), items.end(),
[](data const &a, data const &b) { return a.number < b.number; });
这样写起来一般会方便一点。可读性取决于--对于像这样简单的东西，我认为
// 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;
}
事实证明
您可以将索引数组与值数组分开，但我认为额外的间接级别将证明是速度杀手。最好将它们放在一个结构或
与任何速度关键应用程序一样，您必须尝试一些实际的实现，并对它们进行比较，以确定哪种实现速度最快。
