【排序算法】——归并排序（递归与非递归）含动图

制作不易，三连支持一下吧！！！

---

前言

这篇博客我们将介绍归并排序的原理和实现过程。

---

一、归并排序递归方法实现

基本思想：
归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide andConquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。

归并排序核心步骤：

    ​​​​1.分解： 

将所给序列一分为二，直到区间中只有一个元素时停止。这个过程是递归进行的，通过传递区间参数来控制。

    2. 合并：

相邻两个子数组有序之后，就递归合并这两个子数组，将它们合并成一个新的有序子数组。

 动图演示如下：

归并时，我们是借助一个临时数组tmp来合并两个有序子数组。 

 代码实现如下：

void _MergeSort(int* a, int begin, int end, int* tmp)
{if (begin >= end)return;int mid = (begin + end) / 2;_MergeSort(a, begin, mid, tmp);_MergeSort(a, mid + 1, end, tmp);int begin1 = begin, end1 = mid;int begin2 = mid + 1, end2 = end;int i = begin;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++];}memcpy(a + begin, tmp + begin, sizeof(int) * (end - begin + 1));
}
void MergeSort(int* a, int n)
{int* tmp = (int*)malloc(n * sizeof(int));_MergeSort(a, 0, n - 1, tmp);free(tmp);tmp = NULL;
}

二、归并排序非递归方法实现

同快速排序一样，如果递归深度过深，可能会导致栈溢出，这样的情况下，我们就不能用递归法来实现归并排序。

上篇博客提到：将递归改成非递归的一般方法有两种

一种是直接改循环，如斐波那契数列。

另一种是借助栈或队列，例如快速排序。

这里我们借助栈也无法完成归并排序，因此我们只能选择循环。

代码实现如下：

void MergeSortNonR(int* a, int n)
{int* tmp = (int*)malloc(sizeof(int) * n);if (tmp == NULL){perror("malloc:");return;}int gap = 1;while (gap < n){for (int j = 0; j < n; j +=2*gap){int begin1 = j, end1 = begin1 + gap - 1;int begin2 = end1 + 1, end2 = begin2 + gap - 1;int i = j;if (end1 >= n || begin2 >= n){break;}//处理数组越界的情况if (end2 >= n)end2 = n - 1;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++];}memcpy(a + j, tmp + j, sizeof(int) * (end2 - j + 1));}gap *= 2;}free(tmp);tmp = NULL;
}

---