Merge Sort in Java

归并排序与快速排序算法类似，因为它使用分治法来排序元素。它是最流行和最高效的排序算法之一。它将给定的列表分成相等的两半，对这两半分别调用自身，然后将这两个已排序的半合并。我们需要定义 merge() 函数来执行合并。在本节中，我们将讨论 Java 中归并排序的实现、分步排序、归并排序的复杂度、优点和缺点。

执行归并排序的步骤

归并排序的完整执行过程遵循以下基本步骤：

• 输入 数组 被分成相等的两半。
• 每个半部分会进一步划分，直到我们得到单个元素。
• 开始合并过程，其中元素被比较并按排序顺序排列。
• 合并持续进行，直到整个数组被排序。

此方法可确保元素被系统地比较和合并，从而减少与传统排序技术相比的操作次数。

分治法

归并排序算法使用分治法作为策略。它将一个问题分解为小的子问题或数组。执行排序后，合并已排序的数组以获得最终结果。该算法通过三个基本步骤实现。

• 分：将数组分成两半。
• 治：递归地对两个半部分进行排序。
• 合：合并已排序的两个半部分以生成已排序的数组。

递归算法具有高效率，并在所有情况下提供 O(n log n) 的时间复杂度。

归并排序的工作原理

为了理解归并排序算法的工作原理，让我们看一个未排序的数组。假设数组的元素是：

根据归并排序算法，首先将给定的数组分成相等的两半。归并排序不断地将列表分成相等的几部分，直到无法进一步划分。

由于给定数组中有八个元素，因此它被分成两个大小为 4 的数组。

再次，将这两个数组分成两半。由于它们的大小为 4，因此将它们分成大小为 2 的新数组。

再次，划分这些数组以获得无法进一步划分的原子值。

现在，以相同的方式将它们组合起来。

在组合时，首先比较每个数组的元素，然后将它们按排序顺序合并到另一个数组中。

因此，首先比较 12 和 31，它们都在排序位置。然后比较 25 和 8，在两个值的列表中，将 8 放在前面，然后是 25。然后比较 32 和 17，对它们进行排序，将 17 放在前面，然后是 32。之后，比较 40 和 42，并按顺序放置它们。

在下一次组合迭代中，现在比较包含两个数据值的数组并将它们合并到一个数组中。这会得到两个已排序的数组。

最后，合并完整的数组以获得最终的排序数组。

现在，数组已完全排序。

算法

在以下算法中，arr 是给定的数组，beg 是起始元素，end 是数组的最后一个元素。

归并排序的重要部分是 mergeSort 函数。此函数执行两个已排序的子数组 A[beg…mid] 和 A[mid+1…end] 的合并，以构建一个已排序的数组 A[beg…end]。因此，merge 函数的输入是 A[], beg, mid, 和 end。

Java 归并排序程序

以下 Java 程序使用 递归 实现归并排序。

输出

 
Sorted Array:
1 2 3 4 5 6 7 8   

复杂度分析

时间复杂度

• 最佳情况复杂度：当不需要排序时发生，即数组已排序。归并排序的最佳情况时间复杂度为 O(n logn)。
• 平均情况复杂度：当数组元素混乱，既不完全升序也不完全降序时发生。归并排序的平均情况时间复杂度为 O(n logn)。
• 最坏情况复杂度：当需要按反序排序数组元素时发生。这意味着我们需要按升序对数组元素进行排序，但其元素是按降序排列的。归并排序的最坏情况时间复杂度为 O(n logn)。

空间复杂度

归并排序的合并步骤需要额外的空间，因此在辅助空间方面为 O(n)。

归并排序的优点

• 专注的效率：归并排序具有可预测的 O(nlogn) 运行时间，因为它始终以线性时间运行。
• 作为稳定的排序算法：它能够保持相等元素的顺序，使其成为需要稳定性的用例的首选。
• 与链表流畅配合：归并排序推荐用于链表，因为没有数组索引，而是直接使用指针。
• 适用于大量数据：与冒泡排序或插入排序相比，归并排序对大型数据集更有效，后两者在数据集较大时效率会降低。

归并排序的缺点

• 需要额外的内存：这种排序形式不是原地排序，因为需要额外的内存来分配存储。
• 在小型数据集上性能较差：在较小的数组中，归并排序的性能比快速排序慢，特别是考虑到递归性质和所需的额外内存开销。
• 并非在所有情况下都最优：归并排序对于简单的排序算法或小型且接近排序的数组效果不佳；插入排序和快速排序是更优选的选项。

归并排序可确保效率但不是原地排序，而快速排序通常更快，但最坏情况下的场景是 O(n²)。

何时使用归并排序？

归并排序最适合以下场景：

1. 需要稳定性：当保持相等元素的相对顺序很重要时。
2. 需要对链表进行排序：由于其基于指针的合并，它可以有效地对链表进行排序。
3. 对大型数据集进行排序：即使对于大量数据，它也表现良好，这与冒泡排序或选择排序不同。
4. 需要外部排序：它对于排序存储在外部存储设备上的数据很有用。

如果内存使用是一个问题，快速排序或堆排序可能是更好的选择。

结论

归并排序是一种强大而高效的排序算法，可保证所有情况下的性能均为 O(n log n)。它广泛用于对大型数据集、链表和外部排序应用程序进行排序。尽管存在内存开销，但其稳定性和一致的性能使其成为排序操作中不可或缺的工具。