Java中的合并排序程序：合并排序和快速排序之间的区别

JAVA中的归并排序程序介绍

顾名思义，JAVA中的归并排序程序是一种排序算法。 它被经典地概念化为 JAVA 中的分而治之算法。 Java 中的归并排序程序通过递归地将输入数组分解为两个或多个其组成子问题来工作，直到这些子问题简单到可以直接解决。

组成子问题可以与父问题相似或有些相关。 然后将每个子问题的单独解决方案组合起来以获得原始父问题的解决方案。

Java 中的归并排序程序是如何工作的？

如前所述，JAVA 中的归并排序程序是一种分而治之的算法。 这是一种稳定的排序，这意味着数组元素在整个排序过程中保持其相对于彼此的原始位置。

• 划分： 在这一步中，输入数组被分成两个组成部分。 对所有得到的半阵列不断重复此步骤，直到没有更多的半阵列可以进一步划分。
• 征服：在这一步中，将分割后的数组从下到上排序合并，达到最终排序后的数组。

Java中快速排序和合并排序程序的区别

尽管功能相似，但必须重点强调 JAVA 中快速排序和合并排序之间的根本区别。

• 机制：快速排序是一种内部的就地排序算法，而归并排序是一种外部的就地排序算法。 在快速排序中，元素是根据称为枢轴的关键元素进行排序的。 枢轴通常是输入数组中的中间值。 值小于枢轴的元素被推到枢轴的左侧，而具有更大值的元素被推到枢轴的右侧。 这里，将左侧称为左分区，将右侧称为右分区。 相反，归并排序将一个数组重复拆分为两个子数组（n/2），直到只剩下一个元素。 然后它组合子数组以形成排序数组。
• 应用：虽然快速排序适用于小型数组，但合并排序适用于任何数组，无论其大小。
• 速度：在快速排序的情况下，数据集越小，算法越快。 另一方面，Mergesort 以一致的速度处理所有数据集。
• 空间需求和内存使用：如前所述，归并排序是一种外部的、异地排序算法。 它的空间复杂度是O(n)。 因此，需要额外存储 (O(n)) 来对辅助数组进行排序。

另请阅读： Java 中的文字类型及示例

JAVA中归并排序程序的时间复杂度分析

JAVA中的归并排序程序的时间复杂度为O(n*log n)。 根据二分搜索，每当一个数字在每一步中被分成两半时，它都可以用对数函数'log n'来表示。 步数（最多）可以用 log n +1 表示。 任何子数组的中间都是 O(1)。

因此，要合并子阵列，将需要 O (n) 的运行时间。 因此，在 JAVA 中合并排序程序的总时间变为 n (log n +1)。 在所有三种情况（最差、平均和最佳）中，这相当于 O (n*log n) 的时间复杂度，因为合并排序总是需要线性时间来合并两半。

从世界顶级大学在线学习软件课程。 获得行政 PG 课程、高级证书课程或硕士课程，以加快您的职业生涯。

加起来

正如人类的排序数据在逻辑上是合理的并且更容易理解一样，排序数组对于计算机来说更易于管理。 这就是 JAVA 中的归并排序程序的优势所在。 它是一种高效的、通用的、基于比较的排序算法。

如果您有兴趣了解有关 Java 全栈软件开发的更多信息，请查看 upGrad 和 IIIT-B 的全栈软件开发执行 PG 计划，该计划专为在职专业人士设计，提供 500 多个小时的严格培训，9+项目和任务、IIIT-B 校友身份、实用的实践顶点项目和顶级公司的工作协助。