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

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

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

C++ STL 中的 std::sort() 函数是一种混合排序算法,提供 O(nlogn) 的平均和最坏情况时间复杂度。 它使用的排序算法称为 Introsort
Introsort 是快速排序和堆排序的组合,它从快速排序开始,如果递归深度超过基于被排序元素数量的级别,则切换到堆排序。

原创文章,作者:ItWorker,如若转载,请注明出处:https://blog.ytso.com/264168.html

(0)
上一篇 2022年6月7日
下一篇 2022年6月7日

相关推荐

发表回复

登录后才能评论