C++中的快速排序很慢
我有9个以矩阵形式存在的值，需要根据这些值计算中值作为模拟过程的一部分。C++中的快速排序很慢
我在C++中使用快速排序（即qsort（）），这会导致进程运行缓慢（因为此进程会重复执行几次）。
有没有更好的排序算法，我可以使用？
排序得到的中位数是非常低效的，您可以使用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将修改矢量/ array v。Make ac opy首先如果你需要保留原件。
插入排序..
在小数据集可以使用不同的算法来获得最佳性能。一旦数据集增长，QuickSort就会闪耀。
有不同的方法。您可以在插入时对数据结构进行排序，并且有对整个数据集进行排序的地方。你只需要找到你的最佳算法。
插入排序应该是一个更快的随机数据smidge，不是吗？ – 2009-07-30 19:32:30
实际上，当分区或列表的大小变得非常小时，一些快速排序会自动使用选择排序。 – 2009-07-30 19:34:33
@Jeremy也许这是插入排序... – 2009-07-30 19:35:23
就像一个人提到的那样，没有必要完全排序以获得中位数。
STL有排序算法通常可以执行比较内联。它还具有比由qsort保证的更智能的算法，其中O（NlgN）的最坏情况为。
嗨，谢谢。所以我不需要完全排序来获得中位数？在那种情况下，是否有更好的方法来获得结果？谢谢。 – 2009-07-30 19:32:51
RE点2：虽然可能在空间上有所折衷。 （如二叉树排序） – 2009-07-30 19:33:11
@Bi：有一个线性算法的中位数 - 请参阅单个评论的链接。 – EFraim 2009-07-30 19:35:04
只有9个值？ Quicksort是矫枉过正。
当处理较小的数据集时，可能使用插入排序，冒泡排序或其他更简单的排序算法。
性能
冒泡排序有最坏情况和平均复杂度都О（N²），其中n是要排序的项目数。存在许多排序算法，其中O（n log n）的最坏情况或平均复杂度明显更好。甚至其他的О（n²）排序算法，例如插入排序，往往比气泡排序具有更好的性能。因此，当n很大时，冒泡排序并不是一种实用的排序算法。
但是，您不必按照其他人的建议排序来获得中位数。
仅使用快速排序9个值将是相当低效的。对于如此小的样本量，使用选择排序或替换排序更好......这些排序方法的开销很小。
一旦您的样本量达到阈值（也许是50+），Quicksort和Mergesort会真正发光。
在这些情况下，我会编写自己的代码而不是使用内置函数。
请不要推荐冒泡排序，除了对受虐狂！
对于小数值，插入排序是最好的，它对其他应用程序（几乎排序的任何长度的数据）有好处。
编辑：清理格式，强调建议的答案。
我知道一位曾经管理大家都知道的软件公司的大型开发团队的教授。他告诉我们，他必须去澳大利亚旅行，以解决客户的表现问题，当他到达那里时，有一种泡泡式的评论“最终应该改变为更好的东西”。他说，那天他解雇了这家伙，为该公司花费了数千美元的支持。 – 2009-07-30 19:40:33
@jeremy - 我认为经理和QA应该被解雇 - 而不是开发人员...... – Tim 2009-07-30 19:48:04
@时间是的，我同意。但至少它的威慑力足以让人知道那里有人可能会因此而解雇你。 – 2009-07-30 19:51:32
你没有足够的值与快速排序的工作，你应该少用先进的算法（例如：冒泡排序，插入排序，... explanation here
有关联的快速排序的设置，当成本。你没有足够的价值，也没用使用此兽
叫Quicksort一头野兽是......呃......我不知道。单线算法不能成为野兽。 – EFraim 2009-07-30 19:38:04
Err，当我谷歌“单行快速排序”是一吨Haskell点击（和这个问题：P）时唯一得到的。你可以给我一个简单的快速排序在c + +？ :) – 2009-07-30 19:49:09
std :: sort（）算法几乎总是比qsort（）更可取。它通常更容易使用，运行速度更快。
如果您想详细了解，实际上有一系列排序算法。 Stroustrup写入C++编程语言 std :: sort通常不是正确的使用方法。在这种情况下，std :: nth_element（）可能是你想要的。
你不需要完全排序值以找到中值：http://en.wikipedia.org/wiki/Selection_algorithm – 2009-07-30 19:27:37
所以你认为std :: sort会更好。我的样本量是9或30。 – 2009-07-30 19:49:59
有多离奇。我对什么样的数据集总是9和30感兴趣。:)对不起，我很讨厌。 – 2009-07-30 19:53:24