什么是合并排序(merge sort)？

合并排序是一种高效、通用、基于比较的排序算法。合并排序是一种分而治之的算法，由约翰·冯·诺依曼于1945年发明。大多数实现都会产生稳定的排序，这意味着如果两个元素具有相同的值，那么它们在输出中的相对位置与在输入中的相对位置相同。换句话说，具有相等值的元素的相对顺序保留在排序输出中。

合并排序重复地将列表分解为多个发布者，直到每个子列表由单个元素组成，并以一种导致排序列表的方式合并这些发布者。合并排序是一种比较排序，也就是说，它可以对定义了小于关系的任何输入进行排序。

运行时间是考虑选择排序算法的一个重要因素，因为效率通常考虑到速度。合并排序在保证的O（nlog n）时间内运行，这明显快于其他几种排序算法的平均和最坏情况运行时间。

关于合并排序，您需要了解什么

• 在合并排序中，数组被分成两半（n/2）。
• 快速排序的最坏情况复杂性为O（n2），因为在最坏情况下需要进行大量比较。
• 合并排序可以很好地处理任何类型的数据集，而不管其大小（无论大小）。
• 合并排序是一种外部排序方法，其中要排序的数据不能同时存储在内存中，有些数据必须保存在辅助内存中。
• 在数组大小或数据集较大的情况下，合并排序比快速排序效率更高，工作速度更快。
• 对于链接列表，首选合并排序。
• 合并排序不到位，因为它需要额外的内存空间来存储辅助数组。
• 合并排序不显示良好的缓存局部性，这使得合并排序比快速排序慢。
• 合并排序是稳定的，因为两个值相等的元素在已排序的输出中以与在未排序的输入数组中相同的顺序出现。

什么是快速排序(quick sort)？

快速排序（也称为分区交换排序）是一种高效的排序算法。由英国计算机科学家托尼·霍尔（Tony Hoare）于1959年开发并于1961年出版，它仍然是一种常用的排序算法。如果实施得当，它的速度可能是其主要竞争对手merge sort和heapsort的两到三倍。

快速排序是一种分而治之的算法。它通过从数组中选择一个“pivot”元素并根据其他元素是否小于或大于pivot将其划分为两个子数组来工作。然后对子数组进行递归排序。这可以就地完成，需要少量额外的内存来执行排序。

快速排序是一种比较排序，这意味着它可以对定义了“小于”关系（正式称为“总订单”）的任何类型的项目进行排序。快速排序的高效实现不是稳定排序，这意味着相等排序项的相对顺序不会保留。

对快速排序的数学分析表明，平均而言，该算法对n个项目进行排序需要O（n logn）比较。在最坏的情况下，它进行so（n2）比较，尽管这种行为很少见。

关于快速排序，您需要了解什么

• 在快速排序中，数组被分成任意比例。没有将元素数组分成相等部分的强制。
• 合并排序的最坏情况复杂性是O（n logn）。
• 快速排序不能很好地处理大型数据集。
• 快速排序是一种内部排序方法，其中要排序的数据在主内存中一次调整一次。
• 在数组大小或数据集较小的情况下，快速排序比合并排序效率更高，工作速度更快。
• 对于阵列，首选快速排序。
• 快速排序不需要任何额外存储。
• 快速排序具有良好的缓存局部性，这使得快速排序在许多情况下（如在虚拟内存环境中）比合并排序更快。
• 快速排序不稳定；但是，通过在代码中实现一些更改，可以使其保持稳定。

Also Read: Difference Between Array And Pointer

快速排序(quick sort)和以表格形式合并排序(merge sort in tabular form)的区别