【初阶数据结构】归并排序 - 分而治之的排序魔法

前言

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

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

1. 什么是归并排序？

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

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

1.1 归并排序的步骤

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]。

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

---

2. 归并排序的代码实现

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

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

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
void _MergeSort(int* a, int left, int right, int* tmp)
{if (left >= right){return;}int mid = (left + right) / 2;_MergeSort(a, left, mid, tmp);_MergeSort(a, mid + 1, right, tmp);int begin1 = left, end1 = mid;int begin2 = mid + 1, end2 = right;int i = left;while (begin1 <= end1 && begin2 <= end2){if (a[begin1] <= a[begin2]){tmp[i++] = a[begin1++];}if(a[begin1] >= a[begin2]){tmp[i++] = a[begin2++];}}while (begin1 <= end1){tmp[i++] = a[begin1++];}while (begin2 <= end2){tmp[i++] = a[begin2++];}memcpy(a + left, tmp + left, sizeof(int)*(right-left+1));}//归并排序
void MergeSort(int* a, int n)
{int left = 0, right = n - 1;int* tmp = (int*)malloc(n * sizeof(int));if (tmp == NULL) {perror("malloc fail");return;}_MergeSort(a,left,right,tmp);	
}

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

2.1 归并排序代码的关键部分讲解

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

2.1.1 利用递归

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

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

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

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

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

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

其实是这样的，你可以假设现在你有两个有序的数组，你要将这两个数组组成一个有序(升序)的数组，你会这么做：首先，你会分别拿出两个数组中的第一个元素互相比较，发现有其中一个元素的值比另一个要小，你就把那个小的元素的值放到一个你为一个有序(升序)的数组而申请的内存空间中，之后就拿下一个元素跟这个上次那个元素的值进行比较。
到后面，你会发现肯定有个数组里面的元素是没有被选中的，但是我们也不知道是哪一个，所以我们就可以都遍历一遍找到还没有被选中的元素，将它加进到你申请的空间中。

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

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

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

解释：

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

---

3. 归并排序的非递归写法

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

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

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

具体步骤：

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

由此，我们就可以通过上述思想，写出两个版本的代码：
版本1：

void MergeSortNonR(int* a, int n)
{int* tmp = (int*)malloc(sizeof(int) * n);if (tmp == NULL){perror("malloc fail");return;}int gap = 1;while (gap <= n / 2){for (int i = 0; i < n; i += 2 * gap){//划分区间：[begin1,end1][begin2,end2]int begin1 = i, end1 = i + gap - 1;int begin2 = i + gap, end2 = i + 2 * gap - 1;//控制区间的边界if (end1 >= n){end1 = n - 1;begin2 = n;end2 = n - 1;}else if (begin2 >= n){begin2 = n;end2 = n - 1;}else if (end2 >= n){end2 = n - 1;}int j = i;while (begin1 <= end1 && begin2 <= end2){if (a[begin1] <= a[begin2]){tmp[j++] = a[begin1++];}else{tmp[j++] = a[begin2++];}}while (begin1 <= end1){tmp[j++] = a[begin1++];}while (begin2 <= end2){tmp[j++] = a[begin2++];}memcpy(a+i, tmp+i, sizeof(int) * (end2-i+1));}memcpy(a, tmp, sizeof(int) * n);gap *= 2;}free(tmp);tmp = NULL;
}

版本2：

void MergeSortNonR(int* a, int n)
{int* tmp = (int*)malloc(sizeof(int) * n);if (tmp == NULL){perror("malloc fail");return;}int gap = 1;while (gap <= n / 2){for (int i = 0; i < n; i += 2 * gap){//划分区间：[begin1,end1][begin2,end2]int begin1 = i, end1 = i + gap - 1;int begin2 = i + gap, end2 = i + 2 * gap - 1;if (end1 >= n || begin2 >= n){break;}if (end2 >= n){end2 = n - 1;}int j = i;while (begin1 <= end1 && begin2 <= end2){if (a[begin1] <= a[begin2]){tmp[j++] = a[begin1++];}else{tmp[j++] = a[begin2++];}}while (begin1 <= end1){tmp[j++] = a[begin1++];}while (begin2 <= end2){tmp[j++] = a[begin2++];}memcpy(a+i, tmp+i, sizeof(int) * (end2-i+1));}gap *= 2;}free(tmp);tmp = NULL;
}

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