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

问题描述

我在一次采访中被问到这个问题.它们都是 O(nlogn)，但大多数人使用 Quicksort 而不是 Mergesort.这是为什么?

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?

推荐答案

Quicksort 有 O(n²) 最坏情况运行时和 O(nlogn) 平均情况下运行时间.然而，它在很多场景下都优于归并排序，因为影响算法运行时间的因素有很多，如果把它们放在一起，快速排序就会胜出.

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.

此外，通过使用适当的枢轴选择，可以很容易地几乎完全避免快速排序的 O(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::sort)实际上是 introsort，其理论最坏情况为 O(nlogn)，与归并排序相同.它通过限制递归深度并在超过时切换到不同的算法(heapsort)来实现这一点记录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屋！