为什么快速排序优于合并排序？

尽管在这种最糟糕的情况下，面试官会问这样一个问题：， 快速排序 被认为比 合并排序 .由于某些原因，快速排序更适合，尤其是在数组的情况下：

1. 辅助空间： Mergesort使用额外的空间，quicksort只需要很少的空间，并且具有良好的缓存局部性。快速排序是一种就地排序算法。就地分拣意味着不需要额外的存储空间来执行分拣。合并排序需要一个临时数组来合并已排序的数组，因此它不合适，从而使快速排序具有空间优势。
2. 最坏情况： 快速排序的最坏情况 O（n） ^2. ) 可以通过使用随机快速排序来避免。通过选择正确的支点，可以很容易地避免这种情况。通过选择正确的pivot元素来获得一个平均的案例行为，可以使它临时提高性能，并变得像Merge sort一样高效。
3. 参考地点： 快速排序尤其具有良好的缓存局部性，这使得它在许多情况下比合并排序更快，比如在虚拟内存环境中。
4. 合并排序更适用于大型数据结构： Mergesort是一种稳定的排序，与quicksort和heapsort不同，它可以很容易地适应对链接列表和存储在磁盘存储或网络连接存储等访问速度较慢的介质上的超大列表的操作。参考 这 详情

这个 std:：sort（） 在C++ STL中存在的函数是一种混合排序算法，提供了平均和最坏情况下的时间复杂度。 O（nlogn） .它使用的排序算法称为Introsort。

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

相关文章： 为什么数组首选快速排序，链表首选合并排序？

本文由 曼迪星 .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以使用 写极客。组织 或者把你的文章寄去评论-team@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。

如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。