我在一次面试中被问到这个问题。它们都是O(nlogn),但大多数人使用快速排序而不是归并排序。为什么呢?
当前回答
快速排序和合并排序的小增加。
它还可以依赖于排序项的类型。如果访问项、交换和比较不是简单的操作,就像比较平面内存中的整数一样,那么归并排序可能是更可取的算法。
例如,我们在远程服务器上使用网络协议对项目进行排序。
而且,在像“链表”这样的自定义容器中,也没有快速排序的好处。 1. 对链表进行归并排序,不需要额外的内存。 2. 快速排序中对元素的访问不是顺序的(在内存中)
其他回答
快速排序具有更好的平均情况复杂度,但在某些应用中它是错误的选择。快速排序容易受到拒绝服务攻击。如果攻击者可以选择要排序的输入,他可以很容易地构造一个时间复杂度为o(n^2)的最坏情况的集合。
归并排序的平均情况复杂性和最坏情况复杂性是相同的,因此不会遇到相同的问题。归并排序的这一特性也使它成为实时系统的最佳选择——确切地说,因为没有导致它运行得非常非常慢的病理情况。
由于这些原因,我更喜欢归并排序,而不是快速排序。
我想补充的是,到目前为止提到的三种算法(归并排序,快速排序和堆排序)只有归并排序是稳定的。也就是说,对于那些具有相同键的值,顺序不会改变。在某些情况下,这是可取的。
但是,说实话,在实际情况下,大多数人只需要良好的平均性能和快速排序…快速=)
所有排序算法都有其起伏。有关排序算法的概述,请参阅维基百科的文章。
快速排序和合并排序的小增加。
它还可以依赖于排序项的类型。如果访问项、交换和比较不是简单的操作,就像比较平面内存中的整数一样,那么归并排序可能是更可取的算法。
例如,我们在远程服务器上使用网络协议对项目进行排序。
而且,在像“链表”这样的自定义容器中,也没有快速排序的好处。 1. 对链表进行归并排序,不需要额外的内存。 2. 快速排序中对元素的访问不是顺序的(在内存中)
虽然它们都在相同的复杂度类中,但这并不意味着它们都具有相同的运行时。快速排序通常比归并排序更快,因为它更容易编写紧凑的实现代码,它所做的操作也更快。这是因为快速排序通常更快,人们使用它而不是归并排序。
然而!我个人经常会使用归并排序或快速排序变体,当快速排序表现不佳时,它们会降级为归并排序。记住。快速排序平均只有O(n log n)最坏情况是O(n²)归并排序总是O(n log n).在实时性能或响应性是必须的情况下,你的输入数据可能来自恶意来源,你不应该使用简单的快速排序。
这是采访中经常被问到的一个问题,尽管归并排序在最坏情况下性能更好,但快速排序被认为比归并排序更好,特别是对于大输入。以下是快速排序更好的原因:
1-辅助空间:快速排序是一种就地排序算法。就地排序意味着执行排序不需要额外的存储空间。另一方面,归并排序需要一个临时数组来归并已排序的数组,因此它并不到位。
2-最坏情况:快速排序O(n^2)的最坏情况可以通过使用随机化快速排序来避免。通过选择正确的枢轴,可以很容易地避免这种情况。通过选择合适的枢轴元来获得平均情况下的行为,从而提高了算法的性能,达到了与归并排序一样的效率。
3-引用的局部性:快速排序特别展示了良好的缓存局部性,这使得它在许多情况下比归并排序更快,比如在虚拟内存环境中。
4-尾递归:快速排序是尾递归,而归并排序不是。尾递归函数是一种函数,其中递归调用是函数执行的最后一件事。尾递归函数被认为比非尾递归函数更好,因为尾递归可以被编译器优化。