这不是一个算法问题，而是一个实现问题。
我有一个数据结构长这样：
这个设置需要4秒钟来执行两种排序。在3Ghz i5处理器上对4000万个元素进行排序，4秒钟似乎是一个很长的时间; 是否有更快的方法？我正在使用带有Intel编译器的vs2010（具有排序功能，但似乎不支持此类结构体）。
更新：使用std :: sort可以缩短大约0.4秒的运行时间，调用方式如下：
尽管只有一次排序调用（到GradientOrdering例程），但结果算法需要5秒，比qsort方法多1秒。看起来std::sort暂时是胜利者。
更新3：看起来英特尔的tbb::parallel_sort是获胜者，在我的系统上将单个排序的运行时间降至0.5秒（因此，两个排序为1.0秒，这意味着它从最初的4.0秒缩放得非常好）。我尝试使用Microsoft提出的并行花哨方法here，但由于我已经在使用tbb，而且
我还使用了@gbulmer的建议（真的是敲醒我头脑的意识），即我已经有了原始索引，所以不需要进行第二次排序，我只需要将第一个数组中的索引分配到第二个数组中，并按照排序顺序进行排序。我可以利用这种内存使用，因为我只在至少拥有4 GB RAM的64位机器上部署（提前工作出这些规格是很好的）; 没有这些知识，第二次排序将是必要的。
@gbulmer的建议提供了最大的加速，但原始问题询问最快的排序。 std :: sort是最快的单线程，parallel_sort是最快的多线程，但没有人给出这个答案，所以我把检查交给了@gbulmer。
struct MyStruct {
float val;
float val2;
int idx;
}
我需要遍历一个大约有四千万个元素的数组，并将“val”字段分配为该元素，将“idx”字段分配为该元素的索引。
接下来我会调用：
MyStruct* theElements = new MyStruct[totalNum];
qsort(theElements, totalNum, sizeof(MyStruct), ValOrdering);
然后，一旦我填写了val2，就可以使用相反的过程进行操作。
qsort(theElements, totalNum, sizeof(MyStruct), IndexOrdering);
哪里
static int ValOrdering(const void* const v1, const void* const v2)
{
if (((struct MyStruct*) v1)->val < ((struct MyStruct*) v2)->val)
return -1;
if (((struct MyStruct*) v1)->val> ((struct MyStruct*) v2)->val)
return 1;
return 0;
}
和
static int IndexOrdering(const void* const v1, const void* const v2)
{
return ((struct MyStruct*) v1)->idx- ((struct MyStruct*) v2)->idx;
}
这个设置需要4秒钟来执行两种排序。在3Ghz i5处理器上对4000万个元素进行排序，4秒钟似乎是一个很长的时间; 是否有更快的方法？我正在使用带有Intel编译器的vs2010（具有排序功能，但似乎不支持此类结构体）。
更新：使用std :: sort可以缩短大约0.4秒的运行时间，调用方式如下：
std::sort(theElements, theElements + totalPixels, ValOrdering);
std::sort(theElements, theElements + totalPixels, IndexOrdering);
并且
bool GradientOrdering(const MyStruct& i, const MyStruct& j){
return i.val< j.val;
}
bool IndexOrdering(const MyStruct& i, const MyStruct& j){
return i.idx< j.idx;
}
在谓词中添加“inline”关键字似乎没有关系。由于我有一个四核机器，规范也允许，所以下一步我将尝试某种多线程排序。
更新2：在@SirGeorge和@stark的建议下，我查看了通过指针重定向完成的单个排序：
bool GradientOrdering(MyStruct* i, MyStruct* j){
return i->val< j->val;
}
bool IndexOrdering(MyStruct* i, MyStruct* j){
return i->idx< j->idx;
}
尽管只有一次排序调用（到GradientOrdering例程），但结果算法需要5秒，比qsort方法多1秒。看起来std::sort暂时是胜利者。
更新3：看起来英特尔的tbb::parallel_sort是获胜者，在我的系统上将单个排序的运行时间降至0.5秒（因此，两个排序为1.0秒，这意味着它从最初的4.0秒缩放得非常好）。我尝试使用Microsoft提出的并行花哨方法here，但由于我已经在使用tbb，而且
parallel_sort的语法与std::sort的语法相同，因此我可以使用早期的std::sort比较器来完成所有工作。我还使用了@gbulmer的建议（真的是敲醒我头脑的意识），即我已经有了原始索引，所以不需要进行第二次排序，我只需要将第一个数组中的索引分配到第二个数组中，并按照排序顺序进行排序。我可以利用这种内存使用，因为我只在至少拥有4 GB RAM的64位机器上部署（提前工作出这些规格是很好的）; 没有这些知识，第二次排序将是必要的。
@gbulmer的建议提供了最大的加速，但原始问题询问最快的排序。 std :: sort是最快的单线程，parallel_sort是最快的多线程，但没有人给出这个答案，所以我把检查交给了@gbulmer。
std::sort= 更多的类型信息和更多的内联机会。 - James McNellis