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


当前回答

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

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

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

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

1 Sedgewick,算法

其他回答

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

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

当我试验这两种排序算法时,通过计算递归调用的次数, 快速排序始终比归并排序具有更少的递归调用。 这是因为快速排序有枢轴,而在下一个递归调用中不包括枢轴。这样快速排序可以比归并排序更快地达到递归基本情况。

为什么快速排序很好?

QuickSort takes N^2 in worst case and NlogN average case. The worst case occurs when data is sorted. This can be mitigated by random shuffle before sorting is started. QuickSort doesn't takes extra memory that is taken by merge sort. If the dataset is large and there are identical items, complexity of Quicksort reduces by using 3 way partition. More the no of identical items better the sort. If all items are identical, it sorts in linear time. [This is default implementation in most libraries]

快速排序总是比归并排序好吗?

不是真的。

归并排序是稳定的,但快速排序不是。所以如果你需要输出的稳定性,你可以使用归并排序。在许多实际应用中需要稳定性。 现在内存很便宜。因此,如果Mergesort使用的额外内存对您的应用程序不是至关重要的,那么使用Mergesort也没有什么害处。

注意:在java中,Arrays.sort()函数对基本数据类型使用快速排序,对对象数据类型使用归并排序。因为对象消耗内存开销,所以为归并排序增加一点开销对于性能来说可能不是什么问题。

参考:在Coursera上观看普林斯顿算法课程第三周的快速排序视频

同时考虑时间和空间的复杂性。 归并排序: 时间复杂度:O(nlogn), 空间复杂度:O(nlogn)

快速排序: 时间复杂度:O(n²), 空间复杂度:O(n)

现在,他们各自在一个场景中获胜。 但是,使用随机枢轴,您几乎总是可以将快速排序的时间复杂度降低到O(nlogn)。

因此,在许多应用中,快速排序是首选,而不是归并排序。

与归并排序不同,快速排序不使用辅助空间。而归并排序使用辅助空间O(n)。 归并排序的最坏情况时间复杂度是O(nlogn)而快速排序的最坏情况复杂度是O(n²)这发生在数组已经排序的时候。