为什么Quicksort比mergesort更好？

为什么Quicksort比mergesort更好？

Quicksort具有O（ n 2）最坏情况运行时和O（ n log n
）平均情况运行时。但是，在许多情况下合并排序会更好，因为许多因素会影响算法的运行时间，并且将它们放在一起时，快速排序会胜出。

特别地，经常被引用的排序算法的运行时是指执行比较或对数据进行排序所需的交换次数。这确实是一个很好的性能衡量标准，尤其是因为它独立于底层硬件设计。但是，其他因素（例如引用的局部性（即，我们是否读取了很多可能在缓存中的元素？））在当前硬件上也起着重要作用。特别是Quicksort，几乎不需要额外的空间，并且具有良好的缓存局部性，因此在许多情况下，它比合并排序要快。

此外，通过适当选择枢轴，例如完全随机选择，几乎完全可以避免quicksort的最坏运行时间O（ n 2）。

实际上，quicksort的许多现代实现（特别是libstdc
++的

std::sort

）实际上是introsort，其理论上最坏的情况是O（
n log n ），与归并排序相同。它通过限制递归深度，并在超过log n时
切换到其他算法（heapsort）来实现此目的。 __