analysis - 在比较方面快速排序与合并排序

Question

首先，我在发布这个问题之前已经完成了搜索。我已经看过为什么快速排序比合并排序更好的问题？但它有一些相互矛盾的答案。

根据我的看法，人们说快速排序比合并排序“更快”，因为它的引用位置、缓存命中等。现在，我接受这在实践中很重要，但我的问题纯粹是关于分析——我对递归不感兴趣开销，缓存问题等。此外，当他们说得更快时，答案通常含糊不清，我不确定他们是否指的是执行所花费的时间，因此缓存问题是否与他们的答案相关。

无论如何，我的问题很简单。纯粹就执行的比较次数而言，归并排序总是比快速排序更有效吗？维基百科告诉我是的，这是我一直认为的，但正如我所说，其他人说不同的话。

Answer 1

在最坏的情况下，基本快速排序将在 O(n^2) 时间内运行。考虑如果选择的枢轴总是下一个最小的元素，它相当于插入排序。合并排序没有这个困难。

此外， Mergesort 也是stable，这意味着它保留了等值元素的顺序（因此它有利于“先按此，然后按那个”进行排序），而 Quicksort 则不是。

Mergesort 的最大缺点是大多数实现必须使用 2n 空间来完成，而 Quicksort 可以就地完成（以防空间在您的应用程序中出现问题）。

Quicksort和Mergesort上的各个维基百科都很棒，我建议阅读它们。