归并排序

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

1. 核心思想：

治：将两个有序子数组合并成一个有序数组（关键步骤）。

分：将数组递归拆分成两半，直到子数组长度为1（天然有序）。

递归法：

递归法详解：

首先是单趟：当给你一个区间数组和所需空间和空间起始点和结束点begin,end

首先判断是否为一：为一就结束函数

然后将其切分成左右两趟排好

最后开始排自己的一趟，当begin2大于begin1时就写入tmp数组，结束条件：任意一个begin到end时结束

然后再遍历两个begin，没有遍历完的部分

最后将tmp中的数据copy到指定数组中去。

void _MergeSort(vector& a, vector& tmp, int begin, int end) {
	if (begin >= end) return;
	int mid = (begin + end) / 2;
	_MergeSort(a, tmp, begin, mid);
	_MergeSort(a, tmp, 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])
			tmp[i++] = a[begin1++];
		else
			tmp[i++] = a[begin2++];
	}
	while (begin1 <= end1) tmp[i++] = a[begin1++];
	while (begin2 <= end2) tmp[i++] = a[begin2++];
	copy(tmp.begin() + begin, tmp.begin() + end + 1, a.begin() + begin);
}
void MergeSort(vector& a) {
	if (a.empty()) return;
	vector tmp(a.size());
	_MergeSort(a, tmp, 0, static_cast(a.size() - 1));
}

非递归法：

void xunMerge(vector& a) {
	if (a.empty()) return;
	vector tmp(a.size());
	int gap = 1;
	int n = a.size();
	while (gap < n) {
		for (int i = 0; i < n; i += 2 * gap) {
			int begin1 = i, end1 = min(i + gap - 1, n - 1);
			int begin2 = i + gap, end2 = min(i + 2 * gap - 1, n - 1);
			if (begin2 >= n) { // 第二组全部越界，无需归并
				break;
			}
			int j = i;
			while (begin1 <= end1 && begin2 <= end2) {
				if (a[begin1] <= a[begin2])
					tmp[j++] = a[begin1++];
				else
					tmp[j++] = a[begin2++];
			}
			while (begin1 <= end1) tmp[j++] = a[begin1++];
			while (begin2 <= end2) tmp[j++] = a[begin2++];
			// 复制已归并的部分
			copy(tmp.begin() + i, tmp.begin() + j, a.begin() + i);
		}
		gap *= 2;
	}
}

今天的更新就到这了，如有错误欢迎评论区指出！！！