前言
今天给大家带来比较排序的最后一种，归并排序，这个排序，需要我们对递归，循环控制要有着较强的理解，我相信大家通过前面和小编的一起学习，这里肯定也是得心应手。
1.归并排序的递归实现
1.1 归并排序概念
归并排序（ MERGE-SORT ）是建立在归并操作上的一种有效的排序算法 , 该算法是采用分治法（ Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。 归并排序核心步骤：
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; } }
代码详解如下：
