为什么是快速排序比归并更好？ [英] Why is quicksort better than mergesort?

问题描述

我在接受采访时问到这个问题。他们俩都是O（nlogn），但大多数人使用快速排序，而不是归并。这是为什么呢？

I was asked this question during an interview. They're both O(nlogn) and yet most people use Quicksort instead of Mergesort. Why is that?

推荐答案

快速排序为O（ N ² ）最坏情况下的运行时间和O（ N 登录 N ）平均情况下运行。然而，这是优于归并排序在许多情况下，因为很多因素会影响算法的运行，并考虑当它们放在一起，快速排序胜出。

Quicksort has O(n²) worst-case runtime and O(nlogn) average case runtime. However, it’s superior to merge sort in many scenarios because many factors influence an algorithm’s runtime, and, when taking them all together, quicksort wins out.

在具体地，排序算法的经常被引用的运行时是指比较的次数或必要执行对数据进行排序互换的次数。这的确是一个性能良好的措施，特别是因为它是独立于底层硬件的设计。然而，在其他因素 - 诸如参考局部性（即做我们阅读了大量它们可能是在高速缓存组件的？） - 也起到对当前的硬件的一个重要的角色。快速排序中特别需要很少的额外空间并且显示出良好的高速缓存局部性，并且这使得速度比在许多情况下归并排序

In particular, the often-quoted runtime of sorting algorithms refers to the number of comparisons or the number of swaps necessary to perform to sort the data. This is indeed a good measure of performance, especially since it’s independent of the underlying hardware design. However, other things – such as locality of reference (i.e. do we read lots of elements which are probably in cache?) – also play an important role on current hardware. Quicksort in particular requires little additional space and exhibits good cache locality, and this makes it faster than merge sort in many cases.

此外，它很容易避免的快速排序的最坏情况下的运行澳时间（ N ² ）几乎完全通过枢轴的一个合适的选择 - 如随意拿起它（这是一个很好的策略）。

In addition, it’s very easy to avoid quicksort’s worst-case run time of O(n²) almost entirely by using an appropriate choice of the pivot – such as picking it at random (this is an excellent strategy).

在实践中，快速排序的许多现代化的实现（特别是的libstdc ++的的std ::排序）实际上的 introsort ，其理论最坏情况是O（ N 登录 N ）一样，同样归并排序。它通过限制递归深度，以及切换到不同的算法（堆排序的）实现本一旦它超过日志名词。

In practice, many modern implementations of quicksort (in particular libstdc++’s std::sort) are actually introsort, whose theoretical worst-case is O(nlogn), same as merge sort. It achieves this by limiting the recursion depth, and switching to a different algorithm (heapsort) once it exceeds logn.

这篇关于为什么是快速排序比归并更好？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！