目录

前言

1.归并排序的递归实现

1.1 归并排序概念

1.2 归并排序递归实现

2.归并排序的非递归实现

前言

今天给大家带来比较排序的最后一种，归并排序，这个排序，需要我们对递归，循环控制要有着较强的理解，我相信大家通过前面和小编的一起学习，这里肯定也是得心应手。

1.归并排序的递归实现

1.1 归并排序概念

1.2 归并排序递归实现

这里我们看具体过程：

这里有个细节我们需要注意一下，在我们对数组进行排序的时候我们需要利用另外一个数组，然后在复制回原数组。

 这里我们的具体代码如下：

void _MergeSort(int* a, int*temp,int begin, int end)
{if (begin >= end){return;}int mid = (begin + end) / 2;_MergeSort(a, temp, begin, mid);_MergeSort(a, temp, mid + 1, end);int begin1 = begin, end1 = mid;int begin2 = mid + 1, end2 = end;int i = begin;while (begin1 <= end1 && begin2 <= end2){if (a[begin1] >=a[begin2]){temp[i++] = a[begin2];begin2++;}else{temp[i++] = a[begin1];begin1++;}}while (begin1 <= end1){temp[i++] = a[begin1];begin1++;}while (begin2 <= end2){temp[i++] = a[begin2];begin2++;}memcpy(a + begin, temp + begin, sizeof(int)*(end - begin + 1));
}//归并排序
void MergeSort(int* a,int n)
{int* temp = (int*)malloc(sizeof(int) * n);if (temp == NULL){perror("malloc fail");return;}_MergeSort(a, temp, 0, n - 1);free(temp);temp = NULL;
}

这里由于我们需要使用到另外的数组去进行存储排序，但是由于局部变量在每次函数调用结束后会自动销毁，所以这里我们需要把数组建立在堆区，但是我们创建数组的操作是不能进行递归的，如果递归就会不断出现重复的数组，因此我们这里只需要把排序和复制回元组的操作进行递归，因此这里我们封装函数MergeSort以及函数_MergeSort.

由于这里我们是将数组元素不断分解直到剩一个元素，或者没有元素，然后先进行左右分解区间的排序，最后返回上一级，直到所有的元素都排序完毕，我们就直接结束排序。

这里我给大家详细讲解一下代码：

2.归并排序的非递归实现

对于非递归实现，之前小编给大家讲解了快速排序的非递归实现，但是相对于今天的归并排序，前者和树的前序遍历类似，后者和树的后序遍历类似，对于此类的递归我们，一般是从最小空间到最大空间不断控制，但是这个过程中有很多的细节需要我们自己掌握一下。

这里小编给大家演示一下具体过程：

 这里我们发现gap=gap*2，只有当我们的数组长度等于2的倍数的时候我们才能刚好分组，否则就会出现某些问题，例如：

那么对于这里的越界我们一共可能会出现三种越界情况，我们要对其分别进行控制

具体情况如下：

1.end1越界了，不归并

2.end1没有越界，begin2越界了，也不归并

3.end1没有越界，begin也没越界。end2越界了，我们需要修正end2

这里我们该怎么理解呢？首先我们需要知道一点，我们的分组是在小组已经排好序的情况下分的，所以我们要明白，begin1~end1这段区间是有序的，begin2~end2这段区间是有序的，但是begin1~end2这段不一定有序（如果都存在的话），那么对于情况一，如果end1越界说明这两段区间都不存在，所以我们就不需要将其归并，对于情况二，如果begin2越界了，但是end1没越界，由于begin1~end1，已经有序，所以我们也就不需要归并，对于情况三，如果只是begin2~end2部分越界，那么我们只需要将begin1~end1和begin2到数组末尾出现的元素进行归并即可。

那么我们的代码如下：

void MergeSortNonR2(int* a, int n)
{int* temp = (int*)malloc(sizeof(int) * n);if (temp == NULL){perror("malloc fail");return;}int gap = 1;int i = 0;while (gap < n){int j = 0;for (i = 0; i < n; i = i + 2 * gap){int begin1 = i, end1 = i + gap - 1;int begin2 = i + gap, end2 = i + gap * 2 - 1;if (end1 >n-1&&begin2 > n - 1){break;}else if(end2>n-1){end2 = n - 1;}while (begin1 <= end1 && begin2 <= end2){if (a[begin1] <= a[begin2]){temp[j++] = a[begin1++];}else{temp[j++] = a[begin2++];}}while (begin1 <= end1){temp[j++] = a[begin1++];}while (begin2 <= end2){temp[j++] = a[begin2++];}memcpy(a+i, temp+i, sizeof(int)*(end2-i+1));}gap = gap * 2;}}

 代码详解如下：