C++中的快速排序速度很慢

Question

我有9个矩阵形式的值，需要在模拟过程中计算这些值的中位数。

我在C++中使用快速排序(即qsort())，这会导致进程运行缓慢(因为这个进程会迭代几次)。

有没有我可以使用的更好的排序算法？

Answer 1

排序以获得中位数的效率非常低。您可以改用STL nth_element：

#include <algorithm>

// Assuming you keep the elements in a vector v of size len

std::nth_element( v.begin(), v.begin()+len/2, v.end() );
median = v[len/2];

 //... or, if the elements are in a simple array v[len], then

std::nth_element( v, v+len/2, v+len );
median = v[len/2];

注意: nth_element将修改向量/数组v。如果需要保留原件，请先制作副本。

Answer 2

请，请永远不要推荐泡泡排序，除非受虐狂！

对于较小的值，insertion sort是最好的，它适用于其他应用程序(几乎排序的任何长度的数据)。

编辑:清理了格式，强调了建议答案。

Answer 3

只有9个值？快速排序是过度杀伤力。

在处理较小的数据集时，可以使用插入排序、冒泡排序或其他更简单的排序算法。

Performance

冒泡排序的最坏情况和平均复杂度都是О(n²)，其中n是要排序的项数。存在许多排序算法，它们的最坏情况或平均复杂度为O( n )。甚至其他О(n²)排序算法，如插入排序，往往比冒泡排序具有更好的性能。因此，当n较大时，冒泡排序并不是一种实用的排序算法。

然而，诚然，你甚至不需要像其他人建议的那样排序来获得中位数。