我在一次面试中被问到这个问题。它们都是O(nlogn),但大多数人使用快速排序而不是归并排序。为什么呢?


当前回答

快速排序和合并排序的小增加。

它还可以依赖于排序项的类型。如果访问项、交换和比较不是简单的操作,就像比较平面内存中的整数一样,那么归并排序可能是更可取的算法。

例如,我们在远程服务器上使用网络协议对项目进行排序。

而且,在像“链表”这样的自定义容器中,也没有快速排序的好处。 1. 对链表进行归并排序,不需要额外的内存。 2. 快速排序中对元素的访问不是顺序的(在内存中)

其他回答

实际上,快速排序是O(n2)。它的平均情况运行时间是O(nlog(n)),但最坏情况是O(n2),这发生在在包含很少唯一项的列表上运行时。随机化花费O(n)。当然,这并没有改变最坏的情况,它只是防止恶意用户使您的排序花费很长时间。

快速排序更受欢迎,因为它:

(MergeSort需要额外的内存,与要排序的元素数量成线性关系)。 有一个小的隐藏常数。

快速排序和合并排序的小增加。

它还可以依赖于排序项的类型。如果访问项、交换和比较不是简单的操作,就像比较平面内存中的整数一样,那么归并排序可能是更可取的算法。

例如,我们在远程服务器上使用网络协议对项目进行排序。

而且,在像“链表”这样的自定义容器中,也没有快速排序的好处。 1. 对链表进行归并排序,不需要额外的内存。 2. 快速排序中对元素的访问不是顺序的(在内存中)

快速排序是在实践中最快的排序算法,但有一些病态的情况,可以使它的表现差到O(n2)。

堆排序保证在O(n*ln(n))中运行,并且只需要有限的额外存储空间。但是有许多真实世界的测试表明堆排序比快速排序平均要慢得多。

在c/c++领域,当不使用stl容器时,我倾向于使用快速排序,因为它是构建的 进入运行时,而归并排序没有。

所以我相信,在许多情况下,这只是阻力最小的途径。

此外,对于整个数据集不适合工作集的情况,快速排序的性能可以高得多。

亩! 快速排序并不比归并排序更好,它非常适合于不同类型的应用。

归并排序是值得考虑的,如果速度是本质,糟糕的最差情况性能不能容忍,并且有额外的空间可用

你说他们«他们都是O(nlogn)[…]»。这是错误的。«快速排序使用大约n^2/2比较在最坏的情况下。

然而,根据我的经验,最重要的属性是在使用带有命令式范式的编程语言进行排序时,可以轻松实现顺序访问。

1 Sedgewick,算法