对列表中的项目进行排序是一项普通的任务，并且通常很耗时。术语排序通常是指基于预定的排序关系以升序或降序排列列表中的项目。排序通常旨在进行搜索，这是他在数据处理中的又一项基本活动。想象一下，如果字典中的单词没有被组织或排序，那么在字典中搜索单词将是多么困难。这就是字典中的条目按标准字母顺序保留的原因。只需排序即可完成许多任务和计算。这就是排序算法的用武之地。
排序算法不过是将列表的元素按特定顺序组织的方法，例如最低到最高值，最高到最低值，递增顺序，递减顺序，字母顺序等。最常用的顺序是数字和字典顺序。算法通常使用排序作为关键子例程。整个过程中使用了各种各样的排序算法，每种算法都使用了一套丰富的技术。一种这样流行但同样强大的算法是分而治之算法，它是一种基于多分支递归的算法。快速排序和合并排序是基于除法和征服算法的两种常用算法。
什么是快速排序？
快速排序是一种基于分而治之方法的高效而有效的排序算法，它与将问题分为两个或多个子问题然后递归求解的动态方法非常相似。 如果子问题的大小足够小，那么它们将以简单的方式简单地解决，而不会带来任何麻烦。 快速排序算法也称为分区交换排序，将要排序的列表分为三个主要部分：1)枢轴元素(中央元素)，2)小于枢轴的元素和3)大于枢轴的元素。 枢轴本身在两组之间移动到最终位置，然后递归应用QUICK SORT。
什么是合并排序？
合并排序是另一种基于分而治之的通用排序算法。 它是最受推崇和流行的排序算法之一，旨在有效地对存储在文件中的数据进行排序。 它在最坏的情况下提供O（n log n）的行为，同时使用O（n）的额外存储。 它将集合“A”分为两个较小的集合，然后对每个集合进行排序。 在最后阶段，将这两个排序的集合合并回到大小为n的单个集合中。 这将是排序列表。 该算法非常快，并且也是稳定的排序，并且是链表的理想选择。
快速排序和合并排序的区别
基本
快速排序和合并排序都是基于分裂和征服的排序算法，具有相同的基本原理-将一个问题分为两个或多个子问题，然后递归解决。但是，它们在合并过程和性能方面有所不同。与小排序数据集相比，快速排序通常比其他排序算法（包括合并排序）更好，更快，而无论数据集的类型如何，“快速排序”都能保持一致性。快速排序是数组的理想选择，而合并排序是链表的理想选择。空间复杂度
快速排序算法中的排序是递归完成的，每个递归调用都需要堆栈位置。除了用于合并的单个存储空间外，它不需要用于合并的额外空间。由于它是就地排序算法，因此不需要额外的空间即可执行排序。实际上，它在分割和合并数组时使用相同的数组。另一方面，在“合并排序”中，有几种表示文件或数组中数据的方式，因此它需要诸如子文件或相同大小的数组之类的工作区，这需要额外的空间。最坏情况的复杂性
当分区不平衡时，会发生快速排序的最坏情况，这取决于用于分区的元素，在这种情况下，算法的渐近运行速度与插入排序一样慢。快速排序的最差情况性能是O（n2），请作为练习来使用。但是，可以通过选择正确的枢轴来避免这种情况。另一方面，合并排序的最坏情况发生在必须进行最大数量的比较时。考虑到合并的线性性能，合并排序的最坏情况是O（n log2 n）。性能
尽管“快速排序”和“合并排序”算法均基于“分而治之”的排序方法，但它们的区别在于执行拆分和合并过程的方法不同。对于快速排序，大部分工作是将列表分为两个子列表，这在对子列表进行排序之前进行。对于“合并排序”，大部分工作是合并两个子列表，这是在对子列表进行排序之后进行的。合并排序需要一个临时数组来合并两个子数组，而快速排序不需要额外的数组空间，这使其比Marge排序更节省空间。
总结
快速排序和合并排序算法均基于分而治之的方法进行排序。 但是，它们的区别在于执行拆分和合并过程的方法。 它们基本上遵循相同的原理-将一个问题分为两个或多个子问题，然后递归解决。 在最坏的情况下，合并排序比快速排序更有效，但是在一般情况下，两者的效率相同。 但是快速排序比合并排序更节省空间。 因此，毫无疑问，“快速排序”比“合并排序”更快且更好，但是在某些情况下（例如，比较），它变得无效。
欢迎任何形式的转载，但请务必注明出处，尊重他人劳动成果。
转载请注明：文章转载自 有区别网 [http://www.vsdiffer.com]
本文标题：快速排序和合并排序
本文链接：https://www.vsdiffer.com/vs/quick-sort-vs-merge-sort.html
免责声明：以上内容仅是站长个人看法、理解、学习笔记、总结和研究收藏。不保证其正确性，因使用而带来的风险与本站无关！如本网站内容冒犯了您的权益，请联系站长，邮箱：，我们核实并会尽快处理。