[C++知识库]图解归并排序 -- c语言

归并排序的定义：

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

1. 递归版

算法思路：

1. ?申请一个空间，该空间用来存放合并后的序列
2. 依次取序列中位数，将数列逐步向下拆分为多个数组，直至n个数被拆分为n个组
3. 相邻的两组之间，相互比较，取小尾插，存入申请的空间内，两个顺序序列合并成一个顺序序列，重复该步骤，依次向下归并
4. 每次归并结束后，将申请空间内的有序序列拷贝回数组
5. 最终使完成排序?

?

?

上面的流程大致为：分 -> 排序?-> 合，流程不断重复，然后得到完全有序的序列。那我们就可以分而治之，将问题分解成小问题后处理。8个数的序列拆分为两个 4个数的子序列，排序比较依旧复杂，那就继续拆分，不断将序列拆分成只有单个数的子序列，比较起来就容易了，这就是分而治之的递归思想了。

递归实现：

用于递归的子函数
void _MergeSort(int* a, int begin, int end, int* tmp)
{

	递归结束条件
	if (begin >= end)
	{
		return;
	}

	取中位数
	int mid = (begin + end) / 2;

	_MergeSort(a, begin, mid, tmp);
	_MergeSort(a, mid + 1, end, tmp);

	int begin1 = begin, end1 = mid;
	int begin2 = mid + 1, end2 = end;
	int i = begin1;

	两组数只在各区间内比较，其一越界即结束比较
	while (begin1 <= end && 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++];
	}

	拷贝已完成归并的部分数据
	memcpy(a + begin1, tmp + begin1, (end2 - begin1 - 1) * sizeof(int));
}

void MergeSort(int* a, int n)
{
	int* tmp = (int*)malloc(sizeof(int) * n);
	if (tmp == NULL)
	{
		perror("malloc fail");
		return;

		_MergeSort(a, 0, n - 1, tmp);

		free(tmp);
		tmp = NULL;
	}
}

?

2. 非递归版

递归是在栈上进行的，栈空间不大，递归数据量过大，会导致栈溢出。用非递归的方式实现归排，就不用担心数据量过大的问题了，所以我们来实现一个非递归的归排。

算法思路：

1. ?申请一个空间，该空间用来存放合并后的序列
2. 规定变量gap为每组内的数据个数
3. 两两比较，取小尾插
4. 调整gap大小，不断向下归并
5. 最终合并为一个完全顺序序列

?

?

非递归大方向与递归一致，与递归不同的地方在于不需要取中位数逐步拆分，而是直接用变量gap直接进行拆分，等同于将递归拆分的过程直接省略，一步到位

非递归实现：

void MergeSortNonR(int* a, int n)
{
	int* tmp = (int*)malloc(sizeof(int) * n);
	if (tmp == NULL)
	{
		perror("malloc fail");
		return;
	}

	int gap = 1;
	
	gap - 每组数据个数
	while (gap < n)
	{

		两组数据归并一次
		下次循环起始位置为两个gap之后
		for (int j = 0; j < n; j += 2 * gap)
		{
			int begin1 = j, end1 = j + gap - 1;
			int begin2 = j + gap, end2 = j + gap * 2 - 1;
			int i = begin1;


            对越界问题进行修正     
			
            第一组越界
			if (end1 >= n)
			{
				break;
			}

			第二组全部越界
			if (begin2 >= n)
			{
				break;
			}
			
			第二组部分越界
			if (end2 >= n)
			{
				//修正end2
				end2 = n - 1;
			}


            归并
             
			两组数只在各区间内比较，其一越界即结束比较
			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++];
			}

			拷贝已完成归并的部分数据
			memcpy(a + j, tmp + j, (end2 - j - 1) * sizeof(int));
		}

		增加进行归并的每组数据
		gap *= 2;
		printf("\n");
	}

	free(tmp);
	tmp = NULL;
}

非递归版最重要，最容易疏忽的就是对越界问题的修正，每次两两一组进行归并，若归并过程有一组落单，无对应序列进行归并，便会产生越界问题，如图所示：

图每组序列的下标区间范围，共10个数，因此下标区间应为0~9，但第二次进行归并时 [8,?9]序列 无对应的归并序列，发生第二组序列全部越界的情况。所以我们应对越界进行修正，[8,?9]序列已是有序序列，所以不需要再继续归并，直接break跳出去即可，第一组部分越界的情况同理。而第二组部分越界的情况，则需要进行修正，因为只剩两个序列需要进行归并。我们只需将越界的部分改为该序列最大下标数 9?即可。即为n - 1。

?

该图为修正后的正确结果。?

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?— END —

?祝你们吃饱！