归并排序例题讲解



本文讲解的排序算法是归并排序，作为归并算法，其有着快速排序算法没有的特性，也是面试比较常考的算法之一。本文会重点讲解思路以及代码的实现。

OK，让我们来一场酣畅淋漓的排序冒险吧！！！

归并排序（MergeSort）是一种基于分治法的高效排序算法，具有稳定性和较好的时间复杂度。归并排序的基本思想是将待排序数组递归地分成两个子数组，分别对这两个子数组进行排序，然后再将它们合并成一个有序数组。

我给大家看一下归并排序的动图：

1. 🍉分解：将数组从中间分为两部分，递归地对子数组进行相同的操作，直到子数组的长度为1（即每个子数组只有一个元素，天然有序）。
2. 🍉合并：将两个有序的子数组合并成一个有序数组。合并的过程通过比较两个子数组的元素大小，按序依次放入目标数组。
3. 🍉重复上述步骤，直到所有子数组都合并成一个有序数组。

也许你看到上面的步骤有点云里雾里的感觉，没有关系，下面我将给出一个具体的例子，带着大家，去理解上面的步骤。

🍇例子：假设我们要对数组 [3, 1, 4, 1, 5, 9, 2, 6] 进行归并排序：

1. 将数组不断分成两部分，直到每个部分只有一个元素：
   [3, 1, 4, 1, 5, 9, 2, 6]

• • 分成 [3, 1, 4, 1] 和 [5, 9, 2, 6]
• • 再分成 [3, 1] 和 [4, 1]，以及 [5, 9] 和 [2, 6]
• • 继续分到每个部分只有一个元素：[3], [1], [4], [1], [5], [9], [2], [6]

2. 合并有序子数组：

• • 将 [3] 和 [1] 合并为 [1, 3]，将 [4] 和 [1] 合并为 [1, 4]
• • 将 [5] 和 [9] 合并为 [5, 9]，将 [2] 和 [6] 合并为 [2, 6]
• • 将 [1, 3] 和 [1, 4] 合并为 [1, 1, 3, 4]，将 [5, 9] 和 [2, 6] 合并为 [2, 5, 6, 9]
• • 最后将 [1, 1, 3, 4] 和 [2, 5, 6, 9] 合并为 [1, 1, 2, 3, 4, 5, 6, 9]
• • 最终得到有序数组 [1, 1, 2, 3, 4, 5, 6, 9]。

相信来看完上面的例子，你已经了解了归并排序的玩法了，那么接下来我们就得用代码来实现了。

大家可以对照着这幅图来理解：

可以看到归并排序的思想一定可以用递归来思想，接下来，我先给大家完整的代码，之后会对代码的关键部分讲解：

这里我们采用的是用_MergeSort这个函数写归并排序的核心代码，这种写法的结构也是现在比较推崇的。

为了让大家更好的吸收上述代码的思想，这里我将会详细的讲解代码关键部分的逻辑。

2.1.1 利用递归

我们直到归并排序是采用分治思想的，其原理就是将一个数组拆解成一个一个有序的区间，最后经过比较合并之后才会称为一个有序的数组。那么，我们该如何，将数组拆成一个个区间呢？

利用递归就可以实现。有的人可能会问了，为什么会使用递归呢？

你可以这样想：我每次以数组中间位置的元素为界限，将数组拆分成两半。紧接着，又对已经拆分成两半的那两个数组再次进行这个操作。直至拆到没有元素或者是只剩一个元素为止，所以我们就可以推导出递归的条件为：左区间是否大于等于右区间。

2.1.2 将拆解的数组的元素放到一个临时空间中进行重新排序

这段代码的作用：将拆解的数组的元素放到一个临时空间中进行重新排序。

有的人会问，那最后两个循环是怎么回事？

2.1.3 将在临时空间中排好的数组复制到目标数组中

这里你可以使用for循环，也可以用一个函数memcpy。这里我选择用后者。

当然，里面的参数十分的讲究。

解释：

• a+left：这里不能直接写a。原因是，每一次拷贝会目标数组的位置不都是数组的头。
• tmp+left：这里也不能直接写为tmp。原因是，每一次让待排序数组位置的元素进行排序时，我们要求位置得一一对应。

非递归归并排序的主要步骤：

1. 🍉初始化步长（子数组长度）为 1，这意味着开始时每个元素作为一个单独的有序数组。
2. 🍉两两合并相邻的子数组，将步长长度的相邻子数组进行合并，形成更大的有序子数组。
3. 🍉逐步增加步长，每次将步长翻倍，然后继续合并相邻的子数组，直到整个数组完全排序。

非递归归并排序的核心思想：归并排序的递归版从上到下拆分数组，而非递归版则从下到上逐步合并，模拟递归中“合并”的过程。在这个过程中，我们通过循环控制子数组的长度，每次将相邻的子数组合并成更大的有序数组。

具体步骤：

1. 🍇从长度为 1 的子数组开始，对整个数组进行遍历，每两个相邻的子数组合并成一个长度为 2 的有序子数组。
2. 🍇再次遍历时，将步长翻倍至 2，对整个数组中相邻的两个长度为 2 的有序子数组进行合并，形成长度为 4 的有序子数组。
3. 🍇重复此过程，不断将步长翻倍（4, 8, 16，直到步长大于数组长度），直到整个数组有序。

版本2：

好了，到这里归并排序的内容就已经全部讲完了。如果大家觉得本文写的还不错的话。麻烦给偶点个赞吧！！！

版权声明：

本文来源网络，所有图片文章版权属于原作者，如有侵权，联系删除。

本文网址：https://www.mushiming.com/mjsbk/4157.html