归并排序含非递归版

目录

1.归并排序的原理

 2.实现归并排序

2.1框架

2.2区间问题和后序遍历

2.3归并并拷贝

2.4归并排序代码

2.5测试

3.非递归实现归并排序 

3.1初次实现

3.2测试 

3.3修改

 3.4修改测试

---

1.归并排序的原理

如图所示：

 2.实现归并排序

2.1框架

2.2区间问题和后序遍历

2.3归并并拷贝

2.4归并排序代码

void MergeSort(int*arr,int n)
//将数组和数组的元素个数传递过来
{
	int* a = (int*)malloc(sizeof(int)*n);
	//创建辅助数组
	if (a == NULL)
	{
		perror("malloc fail");
		return;
	}
	_MergeSort(arr,a,0,n-1);
    free(a);
}
void _MergeSort(int*arr,int*a,int begin ,int end)
{
	//检验区间是否有效
	if (begin >= end)
	{
		return;
	}
	//后序遍历
	int mid = (begin + end) / 2;
	//新区间为[begin,mid],[mid+1,end]
	_MergeSort(arr,a,begin,mid);
	_MergeSort(arr,a,mid+1,end);
    //归并
	int begin1 = begin; int end1 = mid;
	int begin2 = mid+1; int end2 = end;
	//两个区间
	int index = begin;
	//新区间第一个元素的下标
	while (begin1 <= end1 && begin2 <= end2)
	{
		if (arr[begin1] <= arr[begin2])
		{
			a[index++] = arr[begin1++];
		}
		else
		{
			a[index++] = arr[begin2++];
		}
	}
	while (begin1 <= end1)
	{
		a[index++] = arr[begin1++];
	}
	while (begin2 <= end2)
	{
		a[index++] = arr[begin2++];
	}
	//将归并好的内容拷贝回原数组
	memcpy(arr+begin,a+begin,(end-begin+1)*sizeof(int));
}

2.5测试

3.非递归实现归并排序 

3.1初次实现

void MergeSortNonR(int* arr, int n)
{
	int* a = (int*)malloc(sizeof(int) * n);
	//创建辅助数组
	int gap = 1;
	//gap=1便是1个元素和1个元素归并
	while (gap < n)
	{
		int i = 0;
		for (i = 0; i < n; i += 2 * gap)
			//i+=2*gap跳过一整个区间
		{
			//两个区间
			int begin1 = i; int end1 = i + gap - 1;
			int begin2 = i + gap; int end2 = i + 2 * gap - 1;
			int index = i;	//新区间第一个元素的下标
			//归并
			while (begin1 <= end1 && begin2 <= end2)
			{
				if (arr[begin1] <= arr[begin2])
				{
					a[index++] = arr[begin1++];
				}
				else
				{
					a[index++] = arr[begin2++];
				}
			}
			while (begin1 <= end1)
			{
				a[index++] = arr[begin1++];
			}
			while (begin2 <= end2)
			{
				a[index++] = arr[begin2++];
			}
			memcpy(arr + i, a + i, sizeof(int) * (2 * gap));
		}
		gap *= 2;
	}
	free(a);
}

3.2测试 

出现了越界问题

程序在打印之前就被迫中止了

 

3.3修改

void MergeSortNonR(int* arr, int n)
{
	int* a = (int*)malloc(sizeof(int) * n);
	//创建辅助数组
	int gap = 1;
	//gap=1便是1个元素和1个元素归并
	while (gap < n)
	{
		int i = 0;
		for (i = 0; i < n; i += 2 * gap)
			//i+=2*gap跳过一整个区间
		{
			//两个区间
			int begin1 = i; int end1 = i + gap - 1;
			int begin2 = i + gap; int end2 = i + 2 * gap - 1;
			if (begin2 >= n)
			{
				break;
			}
			if (end2 >= n)
				end2 = n - 1;//修正区间长度
			int order = end2 - begin1+1;//修正要拷贝的长度
			int index = i;	//新区间第一个元素的下标
			//归并
			while (begin1 <= end1 && begin2 <= end2)
			{
				if (arr[begin1] <= arr[begin2])
				{
					a[index++] = arr[begin1++];
				}
				else
				{
					a[index++] = arr[begin2++];
				}
			}
			while (begin1 <= end1)
			{
				a[index++] = arr[begin1++];
			}
			while (begin2 <= end2)
			{
				a[index++] = arr[begin2++];
			}
			/*int order = 2 * gap;
			if (2 * gap >= n)
			{
				order = n;
			}*/
			memcpy(arr + i, a + i, sizeof(int) * order);
		}
		gap *= 2;
	}
	free(a);
}

 3.4修改测试

至此，归并排序的递归版和非递归版讲解完成，感谢各位友友的来访，祝各位友友前程似锦O(∩_∩)O