归并排序

## 归并排序
![](/media/202205/20210509190848853_1653636996.gif)

归并排序是采用分治法的一个非常典型的应用。其基本思想是：将已有序的子序合并，从而得到完全有序的序列，即先使每个子序有序，再使子序列段间有序

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

**算法描述：**
把长度为n的输入序列分成两个长度为n/2的子序列
2. 对这两个子序列分别采用归并排序
3. 将两个排序好的子序列合并成一个最终的排序序列

[wokwi_归并排序](https://wokwi.com/projects/332802505356345940)|[wokwi_归并排序](https://wokwi.com/projects/334327110703252050)
### 递归实现
![](/media/202205/2022-05-27_153719_556156.png)

归并排序，从其思想上看就很适合使用递归来实现，并且用递归实现也比较简单。其间我们需要申请一个与待排序列大小相同的数组用于合并过程两个有序的子序列，合并完毕后再将数据拷贝回原数组

```c
// 归并排序(主体函数),MergeSort(数组名,数组长度,[排序方向,默认小到大])
// 即每次从待排序列中选出一个最小值,然后放在序列的起始位置,直到全部待排数据排完即可
void MergeSort(int array[], int size, boolean forward = true){
	int* tmp = (int*)malloc(sizeof(int)*size);    // 申请一个与原数组大小相同的空间
	if (tmp == NULL) exit(-1);
	_MergeSort(array, 0, size - 1, tmp, forward);    // 归并排序
	free(tmp);    // 释放空间
}
// 归并排序(子函数),_MergeSort(数组名,区间开始,区间结束,数组空间,[排序方向,默认小到大])
void _MergeSort(int* a, int left, int right, int* tmp, boolean forward){
	// 归并结束条件：当只有一个数据或是序列不存在时,不需要再分解
	if (left >= right) return;
	int mid = left + (right - left) / 2;    // 中间下标
	_MergeSort(a, left, mid, tmp, forward);    // 对左序列进行归并
	_MergeSort(a, mid + 1, right, tmp, forward);   // 对右序列进行归并
	int begin1 = left, end1 = mid;
	int begin2 = mid + 1, end2 = right;
	// 将两段子区间进行归并,归并结果放在tmp中
	int i = left;
	while (begin1 <= end1&&begin2 <= end2){
		// 根据传入的第三个参数,来确定是正向排序(小到大)还是逆向排序(大到小)
		if (forward == true){
			// 将较小的数据优先放入tmp
			if (a[begin1] < a[begin2]) tmp[i++] = a[begin1++];
			else tmp[i++] = a[begin2++];
		}else{
			// 将较大的数据优先放入tmp
			if (a[begin1] > a[begin2]) tmp[i++] = a[begin1++];
			else tmp[i++] = a[begin2++];
		}
	}
	// 当遍历完其中一个区间,将另一个区间剩余的数据直接放到tmp的后面
	while (begin1 <= end1) tmp[i++] = a[begin1++];
	while (begin2 <= end2) tmp[i++] = a[begin2++];
	// 归并完后,拷贝回原数组
	for (int j = left; j <= right; j++) a[j] = tmp[j];
}
```

### 非递归实现
![](/media/202205/2022-05-27_171123_674256.png)

归并排序的非递归算法并不需要借助栈来完成，我们只需要控制每次参与合并的元素个数即可，最终便能使序列变为有序

```c
// 归并排序(主体函数),MergeSortNonR(数组名,数组长度,[排序方向,默认小到大])
// 即每次从待排序列中选出一个最小值,然后放在序列的起始位置,直到全部待排数据排完即可
void MergeSortNonR(int array[], int size, boolean forward = true){
	// 申请一个与待排序列大小相同的空间,用于辅助合并序列
	int* tmp = (int*)malloc(sizeof(int)*size);
	if (tmp == NULL) exit(-1);
	int gap = 1;    // 需合并的子序列中元素的个数
	while (gap < size){
		for (int i = 0; i < size; i += 2 * gap){
			int begin1 = i, end1 = i + gap - 1;
			int begin2 = i + gap, end2 = i + 2 * gap - 1;
			// 最后一组的第二个小区间不存在或是第一个小区间不够gap个,此时不需要对该小组进行合并
			if (begin2 >= size) break;
			// 最后一组的第二个小区间不够gap个,则第二个小区间的后界变为数组的后界
			if (end2 >= size) end2 = size - 1;
			_MergeSortNonR(array, tmp, begin1, end1, begin2, end2, forward);//合并两个有序序列
		}
		// 下一趟需合并的子序列中元素的个数翻倍
		gap = 2 * gap;
	}
	free(tmp);    // 释放空间
}
// 归并排序(子函数),_MergeSortNonR(数组名,数组空间,区间1开始,区间1结束,区间2开始,区间2结束,[排序方向,默认小到大])
void _MergeSortNonR(int* a, int* tmp, int begin1, int end1, int begin2, int end2, boolean forward){
	int j = begin1;
	// 将两段子区间进行归并,归并结果放在tmp中
	int i = begin1;
	while (begin1 <= end1&&begin2 <= end2){
		// 根据传入的第三个参数,来确定是正向排序(小到大)还是逆向排序(大到小)
		if (forward == true){
			// 将较小的数据优先放入tmp
			if (a[begin1] < a[begin2]) tmp[i++] = a[begin1++];
			else tmp[i++] = a[begin2++];
		}else{
			// 将较大的数据优先放入tmp
			if (a[begin1] > a[begin2]) tmp[i++] = a[begin1++];
			else tmp[i++] = a[begin2++];
		}
	}
	// 当遍历完其中一个区间,将另一个区间剩余的数据直接放到tmp的后面
	while (begin1 <= end1) tmp[i++] = a[begin1++];
	while (begin2 <= end2) tmp[i++] = a[begin2++];
	// 归并完后,拷贝回原数组,这里
	for (j; j <= end2; j++) a[j] = tmp[j];
}
```