为什么快速排序比合并排序好

这是数据结构面试中的一个常见问题，即尽管归并排序的最坏情况性能更好，但快速排序被认为比归并排序更好。由于某些原因，快速排序更好，尤其是在数组的情况下：

• 辅助空间：合并排序使用额外的空间，快速排序需要很少的空间并且表现出良好的缓存局部性。快速排序是一种就地排序算法。就地分拣意味着不需要额外的存储空间来执行分拣。合并排序需要一个临时数组来合并已排序的数组，因此它不是就地的，因此快速排序具有空间优势。
• 最坏情况：使用随机快速排序可以避免快速排序 O(n2) 的最坏情况。通过选择正确的支点可以很容易地避免这种情况。通过选择正确的枢轴元素来获得平均案例行为，使其即兴发挥并变得与合并排序一样高效。
• 参考局部性：快速排序尤其表现出良好的缓存局部性，这使得它在许多情况下比合并排序更快，例如在虚拟内存环境中。
• 合并排序更适合大型数据结构：合并排序是一种稳定的排序，与快速排序和堆排序不同，并且可以轻松适应对存储在慢速访问介质(如磁盘存储或网络附加存储)上的链表和非常大的列表进行操作。

C++ STL 中的 std::sort() 函数是一种混合排序算法，提供 O(nlogn) 的平均和最坏情况时间复杂度。 它使用的排序算法称为 Introsort 。

Introsort 是快速排序和堆排序的组合，它从快速排序开始，如果递归深度超过基于被排序元素数量的级别，则切换到堆排序。