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


当前回答

虽然它们都在相同的复杂度类中,但这并不意味着它们都具有相同的运行时。快速排序通常比归并排序更快,因为它更容易编写紧凑的实现代码,它所做的操作也更快。这是因为快速排序通常更快,人们使用它而不是归并排序。

然而!我个人经常会使用归并排序或快速排序变体,当快速排序表现不佳时,它们会降级为归并排序。记住。快速排序平均只有O(n log n)最坏情况是O(n²)归并排序总是O(n log n).在实时性能或响应性是必须的情况下,你的输入数据可能来自恶意来源,你不应该使用简单的快速排序。

其他回答

快速排序并不比归并排序好。对于O(n²)(很少发生的最坏情况),快速排序可能比归并排序的O(nlogn)慢得多。快速排序的开销更小,所以对于小n和速度较慢的计算机,它会更好。但是今天的计算机是如此之快,以至于合并排序的额外开销可以忽略不计,并且在大多数情况下,非常慢的快速排序的风险远远超过合并排序的微不足道的开销。

此外,归并排序将具有相同键的项按原始顺序保留,这是一个有用的属性。

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

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

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

That's hard to say.The worst of MergeSort is n(log2n)-n+1,which is accurate if n equals 2^k(I have already proved this).And for any n,it's between (n lg n - n + 1) and (n lg n + n + O(lg n)).But for quickSort,its best is nlog2n(also n equals 2^k).If you divide Mergesort by quickSort,it equals one when n is infinite.So it's as if the worst case of MergeSort is better than the best case of QuickSort,why do we use quicksort?But remember,MergeSort is not in place,it require 2n memeroy space.And MergeSort also need to do many array copies,which we don't include in the analysis of algorithm.In a word,MergeSort is really faseter than quicksort in theroy,but in reality you need to consider memeory space,the cost of array copy,merger is slower than quick sort.I once made an experiment where I was given 1000000 digits in java by Random class,and it took 2610ms by mergesort,1370ms by quicksort.

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

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

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

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

虽然它们都在相同的复杂度类中,但这并不意味着它们都具有相同的运行时。快速排序通常比归并排序更快,因为它更容易编写紧凑的实现代码,它所做的操作也更快。这是因为快速排序通常更快,人们使用它而不是归并排序。

然而!我个人经常会使用归并排序或快速排序变体,当快速排序表现不佳时,它们会降级为归并排序。记住。快速排序平均只有O(n log n)最坏情况是O(n²)归并排序总是O(n log n).在实时性能或响应性是必须的情况下,你的输入数据可能来自恶意来源,你不应该使用简单的快速排序。