归并排序算法（含Python/Java/C/C++程序）

归并排序算法与快速排序算法类似，都使用分治法来排序元素。它是最流行和最有效的排序算法之一。它将给定的列表分成两半，分别对两半进行递归调用，然后合并这两个已排序的子列表。我们需要定义merge()函数来执行合并操作。

子列表会反复被分成两半，直到列表无法再进一步分割。然后，我们将一对一对的单元素列表合并成两元素列表，在此过程中进行排序。排序后的两元素对被合并成四元素列表，依此类推，直到得到排序后的列表。

让我们来看一下归并排序的算法。

算法

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

归并排序的步骤

步骤 1：将输入数组分成两半，并持续分割，直到无法进一步分割为止。

步骤 2：使用归并排序算法单独对每个子数组进行排序。

步骤 3：按照排序的顺序合并已排序的子数组，形成一个更大的数组。持续此过程，直到两个子数组的所有元素都已合并。

归并排序算法的工作原理

为了理解归并排序算法的工作原理，我们以一个未排序的数组作为输入。

除以

输入数组[39, 28, 44, 11] 被分成两半 [39, 28] 和 [44, 11]。

再次，我们将子数组 [39, 28] 进一步分成两半 [39] 和 [28]。同样，我们将子数组[44, 11] 分成两半[44] 和 [11]。

征服

我们知道只有一个元素的数组已经是排序好的。因此，数组元素[39]、[28]、[44]和[11]已经是排序好的。

合并

开始按照排序的顺序合并已排序的子数组，形成更大的数组。我们将[39]与[28]合并，形成[28, 39]。同样，我们将[44]与[11]合并，形成[11, 44]。

现在，我们将子数组[28, 39] 和[11, 44]按照排序的顺序合并，得到排序后的数组[11, 28, 39, 44]。

Python/Java/C/C++/C# 中的归并排序实现

• Python
• Java
• C
• C++
• C#

输出

Before sorting array elements are: 
39 28 44 11 
After sorting array elements are: 
11 28 39 44 

复杂度分析

时间复杂度

最佳情况复杂度：发生在不需要排序时，即数组已排序。归并排序的最佳时间复杂度为O(n*logn)。

平均情况复杂度：发生在数组元素杂乱无章时，既不是升序也不是降序。归并排序的平均时间复杂度为O(n*logn)。

最坏情况复杂度：发生在数组元素需要按相反顺序排序时。也就是说，如果我们要按升序对数组元素进行排序，但其元素是降序的。归并排序的最坏时间复杂度为O(n*logn)。

空间复杂度

归并排序的空间复杂度为O(n)。这是因为在归并排序中，需要一个额外的变量来交换。

归并排序的应用

• 它用于对大型数据集进行排序。
• 它也用于外部排序（当数据集的大小太大而无法完全加载到内存时）。
• 它用于逆序对计数。
• 在不同编程语言的库方法中，都使用了归并排序。
• 归并排序的一个变体是Tim Sort，它用于Java、Android、Python和Swift。归并排序是稳定的。因此，它优先用于对非原始类型进行排序。
• Sort 使用归并排序。
• 它用于对链表进行排序。

归并排序的优点

• 稳定性：归并排序是一种稳定的排序算法。因此，它保持数组中相等元素的相对顺序。
• 保证的最坏情况性能：归并排序的最坏情况时间复杂度为O(n log n)。因此，即使数据集很大，它也能表现良好。
• 易于实现：分治法的实现相对简单。
• 天然并行：由于子数组是独立处理的，因此适合并行处理。

归并排序的缺点

• 空间复杂度：归并排序在排序过程中需要额外的内存来存放合并的子数组。
• 非原地排序：它不是一种原地排序算法，这意味着需要额外的内存来存储排序后的数据。在内存使用是关注的应用中，这可能是一个缺点。
• 与快速排序相比，归并排序比快速排序慢。这是因为快速排序由于其原地操作而具有更好的缓存友好性。

结论

归并排序算法以其效率、稳定性和可预测的性能而闻名。这些特性使得归并排序成为各种排序任务的可靠选择，尤其是在处理大型数据集时。

关于归并排序算法的 MCQ 练习

问题 1：在归并排序算法中，合并步骤的主要原因是什么？

1. 找到枢轴元素
2. 将两个已排序的子数组合并成一个已排序的数组
3. 原地交换元素
4. 将数组分割成更小的子数组

问题 2：下列哪项最好地描述了归并排序算法在最佳、平均和最坏情况下的时间复杂度？

1. O(n)
2. O(n log n)
3. O(n^2)
4. O(log n)

问题 3：归并排序算法的高空间复杂度主要原因是什么？

1. 递归函数调用
2. 合并过程中使用额外的临时数组
3. 原地交换元素
4. 过多的指针使用

问题 4：下列哪项不是归并排序的特点？

1. 分治法
2. 原地排序
3. 稳定排序
4. O(n log n) 时间复杂度

问题 5：在归并排序算法中，如果要合并的子数组已经排序，会发生什么情况？

1. 算法会不稳定
2. 算法会变慢
3. 算法进行的比较次数会减少
4. 算法需要更多内存