合并排序算法–具有时间复杂性的Python和Java示例

　　在本文中，我们将讨论合并排序算法。我们将看到一些可视化示例来帮助理解算法，然后使用Java和Python代码实现它。

　　什么是合并排序算法？

　　合并排序算法是基于分而治之算法的高效排序算法。它将元素的集合(数组)划分为单个单元，然后以有序的方式合并它们。

　　让我们看一个示例来了解合并排序的工作原理。

　　我们将使用合并排序算法对以下数字数组进行排序：4， 10， 6， 14， 2， 1， 8， 5

　　下图显示了“划分”过程：

　　该数组首先分为两个单独的数组。然后这些阵列也被分割。这种划分一直持续到阵列中的所有元素都成为一个单元。

　　在此阶段之后，合并开始。这是如何发生的：

　　这些元素正在重新分组到数组中，但这次是按排序顺序排列的。就像它们被拆分一样，它们正在被合并。

　　在我们使用代码实现此算法之前，您应该了解我们如何能够按排序顺序收集这些元素。

　　我们将使用将元素重新组合成两个单独数组的部分 - 4，6，10，14和1，2，5，8。下面是一个插图，用于了解我们是如何到达最终数组的：

　　如上所示，我们有两个箭头指向两个数组的第一个索引。将进行比较以找出哪个索引较小。在我们的例子中，1小于4，因此将被推送到合并的数组。然后，红色箭头将移动到下一个索引。那是：

　　将进行另一个比较：2<4?

　　2 小于 4，因此它将被推送到合并的数组，箭头移动到下一个索引。

　　对于下一个比较：

　　4 小于 5，因此 4 将被推送到合并的数组，青色箭头将移动到下一个索引。

　　这种比较将一直持续到合并的数组被填满。如果它到达一个数组变为空的点，则具有剩余元素的数组将按排序顺序复制到合并的数组中。

　　让我们看一些代码示例！

　　Java 中的合并排序示例

　　如果我们想用Java实现合并排序，那会是什么样子：

　　让我们分解代码。

　　在上面，我们创建了数字数组。之后，我们调用该方法对数字进行排序。然后，我们循环遍历排序后的数字数组，并将它们打印到控制台。mergeSort

　　我们通过将数组长度除以二来获得数组的中点。左数组从第一个索引开始到中点，而右数组从中点之后的索引开始到数组结束的位置。

　　然后，我们创建了两个循环，根据元素的位置将元素复制到左侧和右侧数组中。然后，我们在左侧和右侧数组中调用该方法。这将以递归方式分解数组，直到数组被缩减为单个单元(就像我们在上一节中的图像中看到的那样)。mergeSort

　　最后，我们调用该方法以按排序顺序将数组合并为一个数组。让我们看一下该方法中使用的逻辑。merge merge

　　还记得上一节中图像中的箭头吗?我们在这里使用然后用于合并数组来表示它们，其中数字将按排序顺序推入其中。xyz

　　while 循环用于在两个数组上进行比较并更改 的位置，并且当元素被推入合并数组时。xyz

　　Python 中的插入排序示例

　　此处的逻辑与上一节中的逻辑完全相同。上面，我们使用Python实现了合并排序算法。您可以在上一节中找到有关代码工作原理的说明。

　　合并排序的时间复杂度是 O(n*Log n)适用于所有情况(最佳、平均和最差)。

　　结论

　　在本文中，我们了解了合并排序算法的工作原理。然后，我们看到了一些示例以及如何在 Java 和 Python 代码中应用它。