C++中的quicksort很慢

Question

我有9个矩阵形式的值,需要根据这些值计算中值作为模拟过程的一部分.

我在C++中使用quicksort(即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将修改vector/array v.如果需要保留原始文件,请先复制一份.

Answer 2

请不要向masochists推荐泡泡分类!

对于较小的值,插入排序是最好的,它对其他应用程序(几乎任何长度的排序数据)都有好处.

编辑:清理格式,强调建议的答案.

Answer 3

只有9个值？Quicksort是矫枉过正的.

在处理较小的数据集时,可能使用插入排序,冒泡排序或其他更简单的排序算法.

性能

冒泡排序具有最坏情况和平均复杂度？(n²),其中n是被排序的项目数.存在许多排序算法,其具有明显更好的O(n log n)的最坏情况或平均复杂度.即使是其他？(n²)排序算法,例如插入排序,也往往比冒泡排序具有更好的性能.因此,当n很大时,冒泡排序不是一种实用的排序算法.

但是,如果获得批准,您甚至不必像其他人所建议的那样排序获得中位数.