【数据结构初阶】一文带你学会归并排序（递归非递归）

目录

前言

递归实现

代码实现

 非递归实现

代码实现

总结

---

 

前言

归并排序（Merge sort）是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。

作为一种典型的分而治之思想的算法应用，归并排序的实现由两种方法：

• 自上而下的递归（所有递归的方法都可以用迭代重写，所以就有了第 2 种方法）；
• 自下而上的迭代；

和选择排序一样，归并排序的性能不受输入数据的影响，但表现比选择排序好的多，因为始终都是 O(nlogn) 的时间复杂度。代价是需要额外的内存空间。

递归实现

在我们前边的学习过程中，例如合并两个有序数组等问题，我们就使用过归并的思想，本质上来说归并排序还是分治的思想，将大问题化为小问题，然后解决小问题，最终是实现大问题的解决。

 动图演示

 

归并排序的递归实现并不复杂，有以下几个步骤：

1.首先申请一段空间tmp，用来保存以及排好序的部分数据，当所有数据都排序完后，重新拷贝回原数组。

2.对数组数据进行分割，例如二叉树分为左右子树一样，也将数组分割为左右数组，知道左指针left大于等于右指针right时，返回。

3.对以及递归好的数据进行排序，两个区域内的数据进行比较，小的数据插入到tmp数组中，直至到数组的最后一个数据，如果当一个数组提前结束，直接将另外一个数组数据直接拷贝即可。

4.将排序好的tmp数组拷贝回原数组。

代码实现

由于原函数不适合递归，所以我们定义子函数，并且求出left和right进行递归，将数组分为[left,mid]和[mid+1,right]两个部分，切记free我们申请的空间，其余按照思路实现即可。

void _MergeSort(int* a, int left, int right, int* tmp)
{if (left >= right)return;int mid = left + (right - left) / 2;_MergeSort(a, left, mid, tmp);_MergeSort(a, mid + 1, right, tmp);int i = left;int begin1 = left, end1 = mid;int begin2 = mid + 1, end2 = right;while (begin1 <= end1 && begin2 <= end2){if (a[begin1] < a[begin2]){tmp[i++] = a[begin1++];}else{tmp[i++] = a[begin2++];}}while (begin1 <= end1){tmp[i++] = a[begin1++];}while (begin2 <= end2){tmp[i++] = a[begin2++];}for (int i = left; i <= right; i++){a[i] = tmp[i];}
}
void MergeSort(int* a, int n)
{int left = 0;int right = n - 1;int* tmp = (int*)malloc(sizeof(int)*n);if (tmp == NULL){perror("malloc fail");exit(-1);}_MergeSort(a, left, right, tmp);free(tmp);tmp = NULL;
}

 非递归实现

归并的非递归实现起来比递归实现较难一点，但是还是分治的思想，只不过非递归有点类似于二叉树的后序遍历，我们使用gap来控制每次归并时数组内数据个数，例如第一次就是一个一个数据归并成两个数据的有序数组，第二次使用两个数据的有序数组归并成四个数据的有序数组，所以gap是由1开始，并且每次乘2。

非递归实现就是在gap等于1时，将整个数组元素排序成两个两个有序，这个递归实现是不同的。

但是当我们每次将gap乘2时，我们发现数组元素个数不一定是2的次方倍，所以不进行处理时，我们的数组一定会造成越界访问。

我们对每次要归并的数组，第一个数组起始为begin1，结束为end1，第二个数组起始为begin2，结束为end2，所以就会有以下三种情况越界：

1.end1越界，即end1>=n。

2.begin2越界，即begin2>n。

3.end2越界，即end2>=n。

所以我们要对边界进行修正，当边界>=n时，我们将其赋值为n-1，修正如下：

            if (end1 >= n){end1 = n - 1;}if (begin2 >= n){begin2 = n;end2 = n - 1;}if (end2 >= n){end2 = n - 1;}

我们注意到当begin1>=n时，我们将begin2 赋值为n，end2赋值为n-1，我们发现这样的话这段区间就不存在了，这是为什么呢，我们来探究一下。

 

 我们对程序进行以上的处理，发现程序崩溃了，通过调试发现是tmp数组越界了，那么tmp数组为什么会越界呢？

 通过测试发现，本来只有十个数据，所以下标最多到9，但是tmp数组的下标10的位置插入元素，导致越界，这是因为当[begin2,end2]原本不存在，但是我们修正让其存在[9,9]，多插入一个数据，所以导致越界，所以我们做一下修改。

 处理过后就没有下标的越界了。

代码实现

当我们解决这个问题之后，其余代码按照思路实现就好了。

void MergeSortNonR(int* a, int n)
{int* tmp = (int*)malloc(sizeof(int) * n);if (tmp == NULL){perror("maolloc fail");exit(-1);}int gap = 1;while (gap < n){for (int i = 0; i < n; i += 2 * gap){int begin1 = i, end1 = i + gap - 1;int begin2 = i + gap, end2 = i + 2*gap - 1;int InDex = i;if (end1 >= n){end1 = n - 1;}if (begin2 >= n){begin2 = n;end2 = n - 1;}if (end2 >= n){end2 = n - 1;}/*printf("[%d,%d] ", begin1, end1);printf("[%d,%d] ", begin2, end2);*/while (begin1 <= end1 && begin2 <= end2){//printf("%d ", InDex);if (a[begin1] < a[begin2]){tmp[InDex++] = a[begin1++];}else{tmp[InDex++] = a[begin2++];}}while (begin1 <= end1){//printf("%d ", InDex);tmp[InDex++] = a[begin1++];}while (begin2 <= end2){//printf("%d ", InDex);tmp[InDex++] = a[begin2++];}}for (int j = 0; j < n; j++){a[j] = tmp[j];}gap *= 2;}free(tmp);tmp = NULL;
}

总结

我们今天讲解了归并排序的递归和非递归的实现方法，码文不易，希望可以对大家有所帮助。