在比较中，Quicksort vs Mergesort
首先，我在发布这个问题之前完成了搜索。 我已经看过这个问题：为什么quicksort比mergesort更好？ 但它有一些矛盾的答案。
根据我看的地方，人们说quicksort比mergesort更“快”，因为它的参考位置，缓存命中等等。现在，我认为这在实践中很重要，但我的问题纯粹是关于分析 - 我对递归不感兴趣开销，缓存问题等。 此外，答案往往含糊不清，因为当他们说得更快时，他们的意思是什么，我不确定他们是否指的是执行时间，因此如果缓存问题与他们的答案相关。
无论如何，我的问题很简单。 纯粹根据执行的比较次数，mergesort总是比quicksort更有效率？ 维基百科告诉我是的，这是我一直认为的，但正如我所说，其他人说不同的事情。
基本的Quicksort，在最坏的情况下，将运行在O（n ^ 2）时间。 考虑如果选择的轴始终是下一个最小的元素，那么它相当于插入排序。 Mergesort没有这个困难。
此外，Mergesort也是稳定的，这意味着它保留了同等重要元素的顺序（所以这对于“先由此，然后再由此进行排序”是好事），而Quicksort则不然。
Mergesort最大的缺点是大多数实现必须使用2n空间来完成，而Quicksort可以在原地完成（以防空间在应用程序中出现问题）。
Quicksort和Mergesort上的个人wikipedias都非常出色，我建议您阅读它们。
链接地址: http://www.djcxy.com/p/31581.html