快速排序与归并排序：区别与比较

排序是用于按正确顺序排列元素的方法。 它是数据结构和算法中使用的一种技术。 可以使用多种方法进行排序。

快速排序和归并排序都使用分而治之的方法对元素进行排序。 这是一种将元素分成两部分并在重新排列元素后将它们组合起来的方法。 

关键精华

1. 快速排序是一种排序算法，它使用一个枢轴元素将数组分成两个分区并递归排序。 相比之下，合并排序将数组分成两半，分别排序，然后合并。
2. 快速排序的最坏情况时间复杂度为 O(n^2)，但平均而言，它的时间复杂度为 O(n log n)，而归并排序的保证时间复杂度为 O(n log n)。
3. 快速排序是一种就地排序算法，这意味着它不需要额外的内存，而合并排序需要额外的内存来存储合并步骤中的临时数组。

快速排序与归并排序

快速排序是一种排序 算法 它使用分而治之的方法对数组或元素列表进行排序。快速排序效率很高，在实际中得到应用。归并排序是一种分治算法，将数组分为两半。它对于大型数据集很有用。

在快速排序中，您选择任何随机元素并将其命名为枢轴。 如果您对应将哪个元素作为主元感到困惑，则该元素将划分或分区数组。

然后您可以将第一个元素作为枢轴元素。 最坏的情况是o(n^2)。 平均情况为 o (n log n)。 最好的情况是o(n)。  

归并排序是数据结构中最常用和最受尊敬的算法之一。 由于其时间复杂度，与快速排序相比，它具有许多优点。 最坏的情况是o(n log n)。 平均情况为 o (n log n)。 最好的情况是o(n log n)。

对比表

比较参数	快速排序	合并排序
定义	它是排序算法之一，将元素按顺序排列。	它是一种用于通过比较元素对元素进行排序的算法。
太空	它使用最小的空间。	它使用更多的空间。
阵列效率	最好使用较小的阵列。	它适用于所有类型的数组。
工作速度	对于较小的数据集，它将工作得更快。	它对所有数据集保持相同的速度。
排序方法	它使用内部排序。	它使用外部排序。

什么是快速排序？

在快速排序选择主元时，元素对于解决问题非常重要。 一个简单的错误将花费更多时间。 完成分区过程后，将元素一分为二。

例如，一行应包含小于主元的元素，另一行应包含大于主元的元素。

那么下一步就是对元素进行递归排序。 最左边的部分称为左分区。 最右边的部分称为右分区。 将问题一分为二意味着您将其简化为线性时间限制。 这就是其平均时间复杂度的原因。 

当您认为元素很少时，可以使用快速排序。 因为当你尝试对大量元素进行排序时，如果你第一次尝试这样做，你可能会犯错误。 此外，解决较大元素的问题需要更多时间。 

这是一种更简单的方法，因为它需要有限的空间和一些良好的知识。 枢轴元素也会将该元素与其左侧和右侧进行比较。 它曾经这样做，直到所有元素都排列正确 秩序. 

什么是合并排序？

归并排序是一种基于比较的算法。 即使在排序后它仍然保留元素的顺序。 它用于将数组分成两部分。 它将对每个数组进行排序，然后将它们组合在一起。 这种排序技术需要额外的内存空间来对辅助数组进行排序。

由于这会一次又一次地划分元素直到它变成一个，因此这种技术减少了排序时间。 该方法使用三个数组。 前两个数组用于存储一半的元素。 然后下一个用于存储最终排序的数组列表。 

在这个过程之后，每个数组将被递归排序。 归并排序的关键步骤之一是您必须确定断点。 它基本上是识别上升或 降 元素集合中的个数。 然后将它们存储在数组中，最后使用这些技术合并它们。

合并排序是开始分而治之过程的好地方。 缺点是它必须将子数组的所有元素放在一个单独的递归单元中，但答案会很精确。 与归并排序算法相关的重要概念之一是倒置法。

快速排序和归并排序的主要区别

1. 合并排序为您提供精确的值，而不管元素的数量多，但比快速排序需要更多的计算空间。 
2. 与快速排序相比，合并排序要快一些。
3. 快速排序主要基于交换元素。 另一方面，合并排序基于合并排序的数组。
4. 快速排序需要一些额外的内存来进行递归。 但是合并排序需要额外的内存来进行递归和合并。
5. 由于空间需求，快速排序在解决问题时比归并排序更快。

参考资料

1. https://link.springer.com/chapter/10.1007/978-3-540-87744-8_21
2. https://www.mdpi.com/2073-8994/9/9/176

最后更新时间：12 年 2023 月 XNUMX 日