数据结构:归并排序

归并排序

时间复杂度O(N*logN)

如果两个序列有序,通过归并,可以让两个序列合并后也有序,变成一个有序的新数组

对于一个数组,如果他的左右区间都有序,就可以进行归并了

归并的方法

将数组的左右两个有序区间比较,每次都取出一个最小的,然后放入临时数组(不能在原数组上修改,因为修改原数组需要挪动数据,时间复杂度高)

但是对于任意一个数组而言,他的左右区间并不有序,如果想要使用归并排序,就要想办法取出数组的有序区间

这里可以使用递归拆分数组,当数组足够小(每一个区间都只有一个数据时),该区间就一定有序,就可以使用归并排序了

可以设置一个temp数组,用来存储分解的区间并进行排序,归并排序完成后再将temp拷贝回原数组的对应区间,直到递归完全结束(原数组有序)

代码

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;
	int end1 = mid;
	int begin2 = mid + 1;
	int end2 = end;
	int i = begin;
	while (begin1 <= end1 && begin2 <= end2)
	{
		if (a[begin1] < a[begin2])
		{
			tmp[i++] = a[begin1++];
		}
		else
		{
			tmp[i++] = a[begin2++];
		}
	}
	//判断哪个区间全部放入tmp,再将另一个区间全部放入tmp
	while (begin1 <= end1)
	{
		tmp[i++] = a[begin1++];
	}

	while (begin2 <= end2)
	{
		tmp[i++] = a[begin2++];
	}
	//将归并好的区间拷贝会原数组
	memcpy(a + begin, tmp + begin, sizeof(int) * (end - begin + 1));
}

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);

	//释放tmp
	free(tmp);
	tmp = NULL;
}

归并排序的非递归方法

归并排序需要将递归改为循环

不方便使用栈来实现,因为不同于快速排序类似前序遍历,归并排序的递归类似于二叉树的后序遍历

问题核心

归并排序需要两个区间进行归并,

而如果使用栈,则当取到需要归并的两个区间的第二个时

第一个区间就已经被pop出栈了,无法知道哪个区间需要和当前区间归并

解决方法

可以将数组看作一个一个数(一个数就是一个区间),然后每两个就进行归并

将归并后的两个数再看作一个区间,再与其他区间进行归并

即直接从叶子节点向前走(回溯)

可以设置gap = 2^n来归并每组数据

设置每个区间的首尾为b n(begin n),e n(end n)

eg.

由图可知,e1 = b1 + gap - 1,b2 = b1 + gap

后续同理

基础代码框架(存在问题)

根据当前的思路,可以写出大概的代码

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

	int gap = 1;
	while (gap < n)//一直归并到原数组大小
	{
		for (int j = 0; j < n; j += 2 * gap)//保证每一个区间都被取到
		{
			int begin1 = j, end1 = j + gap - 1;
			int begin2 = j + gap, end2 = begin2 + gap - 1;
			int i = j;

			while (begin1 <= end1 && begin2 <= end2)
			{
				if (a[begin1] < a[begin2])
				{
					tmp[i++] = a[begin1++];
				}
				else
				{
					tmp[i++] = a[begin2++];
				}
			}
			//判断哪个区间全部放入tmp,再将另一个区间全部放入tmp
			while (begin1 <= end1)
			{
				tmp[i++] = a[begin1++];
			}

			while (begin2 <= end2)
			{
				tmp[i++] = a[begin2++];
			}

			memcpy(a + j, tmp + j, sizeof(int) * 2 * gap);
		}
		gap *= 2;
	}
	free(tmp);
	tmp == NULL;
}

代码问题(数组越界)

当前代码可能存在数组的越界访问

理论上来讲,除了begin1 = j < n外,其他的begin2, end1, end2都可能越界

因此需要分开处理这些问题

1.end1越界

end1越界(end1后面就没有数据了)说明当前没有第二组数据,而第一组只有一部分,且有序

因此当前这一组就不需要再进行归并了,直接让这一组准备下一层归并

2.begin2越界

begin2越界也不用归并,原因与end1越界相同

3.end2越界

end2越界需要归并,因为在begin2与end2中还存在部分有序数据,因此需要归并组成新区间

但是想要归并就需要修正end2,保证end2不再越界

4.修改后的代码

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

	int gap = 1;
	while (gap < n)//一直归并到原数组大小
	{
		for (int j = 0; j < n; j += 2 * gap)//保证每一个区间都被取到
		{
			int begin1 = j, end1 = j + gap - 1;
			int begin2 = j + gap, end2 = begin2 + gap - 1;
			int i = j;

			if (end1 >= n || begin2 >= n)//end1和begin2越界,跳出当前循环,不归并
			{
				break;
			}

			if (end2 >= n)
			{
				end2 = n - 1;
			}
			while (begin1 <= end1 && begin2 <= end2)
			{
				if (a[begin1] < a[begin2])
				{
					tmp[i++] = a[begin1++];
				}
				else
				{
					tmp[i++] = a[begin2++];
				}
			}
			//判断哪个区间全部放入tmp,再将另一个区间全部放入tmp
			while (begin1 <= end1)
			{
				tmp[i++] = a[begin1++];
			}

			while (begin2 <= end2)
			{
				tmp[i++] = a[begin2++];
			}

			memcpy(a + j, tmp + j, sizeof(int) * (end2 - j + 1));//使用修正后的区间长度
		}
		gap *= 2;
	}
	free(tmp);
	tmp == NULL;
}