【C语言】归并排序递归和非递归—

一、归并排序思想

1.1 基本思想

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

在这里插入图片描述

1.2 大体思路

将数据从中间分成两个子序列
将子序列不断的划分，直到只剩一个数据，该子序列有序了
子序列有序了，就开始两两一合并，直到所有的子序列合并完，排序就完成了。

二、实现归并排序（递归）

思路：

前提：
申请一个临时数组tmp，因为我们不能在原数组归并，不然会造成覆盖，需要在临时归并，在拷回原数组里。
由于创建了临时数组，我们就需要在创建一个子函数用来专门递归，不然每次调用都会申请空间

子函数思路：

将序列从中间分成两个区间[left，mid] [mid + 1，right]，调用递归，直到只剩一个数据，一个数据就表示有序了。
在把递归的两个区间进行合并，begin1和end2表示左序列，begin1和end2表示右序列，比较两个序列的值插入到临时数组里，其中肯定会有一个先结束，当其中一个序列拷贝完了就停止拷贝。
把剩下未合并的数据，全部放到tmp数组里。
最后在tmp数组的数据拷到原数组里。

// 子函数：用来递归
void _MergeSort(int* a, int left, int right, int* tmp)
{if (left >= right)return;int mid = (left + right) >> 1;// 分区[left, right] -> [left, mid] [mid + 1, right]_MergeSort(a, left, mid, tmp);_MergeSort(a, mid + 1, right, tmp);// 标识归并两个有序的开始和结束int begin1 = left, end1 = mid;int begin2 = mid + 1, end2 = right;// 两个序列合并，肯定会有一个先结束int index = left;while (begin1 <= end1 && begin2 <= end2){if (a[begin1] < a[begin2]){tmp[index++] = a[begin1++];}else{tmp[index++] = a[begin2++];}}// 处理剩下未合并完的数据，合并完的肯定不会进入循环while (begin1 <= end1)tmp[index++] = a[begin1++];while (begin2 <= end2)tmp[index++] = a[begin2++];// tmp的数据拷贝到原数组，闭区间所以拷贝个数要加1memmove(a + left, tmp + left, (right-left+1) * sizeof(int));
}void MergeSort(int* a, int n)
{// 创建临时数组，用来存放合并完的数据int* tmp = (int*)malloc(n * sizeof(int));_MergeSort(a, 0, n - 1, tmp);free(tmp);
}

细节注意：

归并的时位置都是相对位置，如[2,2][3,3]合并，合并完存放在tmp数组里也要是[2,3]，所以两个序列都是两个区间的相对位置，所以左序列：begin1 = left，end1 = mid，右序列：begin2 = mid+1，end2 = right
index = left，不是index = 0，也是为了将原数组的相对位置的数据合并到tmp数组的相对位置，如a[2]就要放到tmp[2]
拷贝数据函数memmove使用，memmove（目的地址dst，源地址src，拷贝数据个数（单位字节））
同样拷贝数据时，也要注意相对位置，如memmove(a, tmp, (right-left+1) * sizeof(int))，这样每次就会从tmp下标0开始拷贝，并不是相对位置。
子函数使用的闭区间，传的是拷贝数据个数，需要+1，如：[0，9]，一个10个数

三、实现归并排序（非递归）

递归还是那个栈溢出问题，上一篇快排非递归版本详细说明和举例过了，这里不在一一说明了。快速排序

在这里插入图片描述

gap表示每组数据的个数，一次两组数据归并，得出2*gap就是一次归并的个数，通过每组个数(gap)推导出每组数据的区间，如[0，0]和[1，1]归并，gap为1，i = 0，得出[i，i + gap - 1]，[i + gap，i + 2*gap - 1]。
排下一次就需要i += 2 * gap，就可以访问下一次归并的起始位置了，如果先是[0，0]和[1，1]归并，在就是[2，2]和[3，3]归并
归并好的数据需要放入到临时数组大家可以通过上图代入值。

这是只是单趟排好多组的样子，这里模拟递归最后一层的情况，和递归相反，我们是从直接最后一层开始归并，递归还需要慢慢的分区递归下来开始归并。
想要整体排好序，gap每次就乘以2，直到gap为n/2，就是说把未排序的数据分成两组数据，两组数据归并完就排好了序。

每次单趟归并完就把临时数组的数据拷回原数组里，再用原数据归并，直到排好序，如下图
在这里插入图片描述

3.1 实现思路：

同样也需要创建一个临时数组tmp，不能在原数据归并会覆盖。
gap为每组数据个数，先从gap为1，一次两组数据归并，模拟递归最后一层的归并，如：[0,0]和[1,1]归并
通过每组个数(gap)推导出每组数据的区间，得出两组数据区间是[i，i + gap - 1]，[i + gap，i + 2*gap - 1]。
i需要加上2*gap，原来的区间已归并好了，所以需要指向下一次归并的起始位置，直到 i >= n结束，循环条件就要设为i < n，表示排好差距为gap的多组数据。
排好差距为gap多组数据后，gap*2，下一趟需下一趟归并的一组数据个数翻倍，直到gap为gap >= n结束，>=就只有一个组数据，不能归并，循环条件就是gap < n，就是说把未排序的数据分成两组数据，两组数据归并完就排好了序。
把临时数组的数据拷到原数组。

void MergeSortNonR(int* a, int n)
{int* tmp = (int*)malloc(n * sizeof(int));assert(tmp);int gap = 1;	// 每组的数据个数// gap < n，就说明有两组数据才能归并while (gap < n){for (int i = 0; i < n; i += gap * 2){// [i, i + gap - 1] [i + gap, i + gap * 2 - 1]// 如：[0, 0] 和 [1, 1]......// 标识需归并两组数据的范围int begin1 = i, end1 = i + gap - 1;int begin2 = i + gap, end2 = i + gap * 2 - 1;// 归并int index = i;while (begin1 <= end1 && begin2 <= end2){if (a[begin1] < a[begin2]){tmp[index++] = a[begin1++];}else{tmp[index++] = a[begin2++];}}// 剩余未归并完的数据全部放入tmp里while (begin1 <= end1){tmp[index++] = a[begin1++];}while (begin2 <= end2){tmp[index++] = a[begin2++];}}// 当前gap多组都归并完了，在全部拷过去（一次拷全部）memmove(a, tmp, n * sizeof(int));gap *= 2;	// 下一趟归并的一组数据个数翻倍}free(tmp);
}

3.2 越界处理

上面的代码，我正好拿2的指数，8个数据测试的，如果不是2的指数， $2^3$ ， $2^4$ 等…，就会越界，分组无法平分，肯定会导致一方越界，一共有3种越界。

在这里插入图片描述
越界情况：

右区间不存在
左区间缺少值
右区间超过数据长度

越界情况1和2可以只需处理一个右区间不存在就可以了，为什么呢？

右区间不存在的话，包含了左区间缺少值的情况，左区间同时也是在原数组中是有序的，所以直接跳出不用拷贝，只拷贝归并了的数据。

越界情况3：只需要纠正右区间的结束标识，让结束标识到最后一个数据即可。

处理：

右区间不存在，直接跳出循环break，不进行归并。
右区间超过数据长度，进行修正，右区间结束标识n-1，就是最后一个数据的下标。
由于右区间不存在直接跳出的情况，tmp数组就会有随机值情况，并且左区间在原数组中也是有序的。
上面代码是把当前差距为gap的数据，全部归并好，在全部拷贝到原数据中。
这里就要修改成归并了多少，就拷多少，归并完直接拷贝，需要放进循环里面。

补充说明：
拷贝数据也可以在全部归并好，在全部拷到原数据，只不过越界处理很麻烦，并且没有归并了多少，拷多少来的直观。
在这里插入图片描述

void MergeSortNonR(int* a, int n)
{int* tmp = (int*)malloc(n * sizeof(int));assert(tmp);int gap = 1;	// 每组的数据个数// gap < n，就说明有两组数据才能归并，>=就说明只有一组数据while (gap < n){for (int i = 0; i < n; i += gap * 2){// [i, i + gap - 1] [i + gap, i + gap * 2 - 1]// 如：[0, 0] 和 [1, 1]......// 标识需归并两组数据的范围int begin1 = i, end1 = i + gap - 1;int begin2 = i + gap, end2 = i + gap * 2 - 1;// 右区间不存在if (begin2 >= n)break;// 右区间超过了数据长度，修正成数据的长度if (end2 >= n)end2 = n - 1;// 归并int index = i;while (begin1 <= end1 && begin2 <= end2){if (a[begin1] < a[begin2]){tmp[index++] = a[begin1++];}else{	tmp[index++] = a[begin2++];}}// 剩余未归并完的数据全部放入tmp里while (begin1 <= end1){tmp[index++] = a[begin1++];}while (begin2 <= end2){tmp[index++] = a[begin2++];}// 拷贝数据，归并了多少，就拷多少for (int j = i; j <= end2; j++){a[j] = tmp[j];}}gap *= 2;	// 下一趟归并的一组数据个数翻倍 }
}