目录

前言

一.归并排序概念

二.归并排序(递归版)

思路

2.1(递归版)详细图解

2.2归并排序子函数代码

2.3归并排序主函数

 2.2递归过程

2.3合并过程

2.4归并排序实现(递归版)

三.归并排序(非递归版本)

思路

3.1(非递归版)图解

3.2一趟gap

3.3多趟gap

 3.4归并排序实现(非递归版)

四.全部代码

4.1全部代码

4.2运行结果截图

---

前言

图解归并排序的2种实现方式的区别(递归和非递归版)；含全部代码

一.归并排序概念

归并排序是一种采用分治法（Divide and Conquer）的有效排序算法，其基本步骤包括分解（Divide），解决（Conquer），和合并（Combine）。首先，通过分解，将n个元素分成个含n/2个元素的子序列。接着，利用归并排序法对这些子序列进行递归排序。最后，当这些子序列已完全排序后，进行合并操作，将两个已排序的子序列合并成一个新的有序序列。

此外，从操作的角度来看，归并排序可以进一步被划分为分割和归并两个步骤。分割是将数组二等分，得到的子数组继续二等分，直到每个子数组只剩下一个元素为止。而归并则是不断将原本属于同一个数组的两个子数组归并成一个新的有序表。

 

二.归并排序(递归版)

思路

递归分解 合并 递归返回

1.进入递归，递归到结束条件时，返回到上一层函数的执行。

2.当子问题递归返回时，进行两段区间数组的排序与合并。

3.函数递归结束返回的过程中，会一直返回并且执行并且解决子问题

我们要熟悉递归思想，这里有递归基础，[递归基础]

2.1(递归版)详细图解

 

2.2归并排序子函数代码

//时间复杂度O(N*logN)
//空间复杂度O(N)
void _MergeSort(int* a, int left, int right, int*tmp)
{
	if (left >= right)
		return;
	
	int mid = (left + right) / 2;
	//[left,mid][mid+1,right]有序，则可以合并，现在无序，子问题解决
	_MergeSort(a, left, mid, tmp);
	_MergeSort(a, mid+1,right, tmp);

	//归并[left,mid][mid+1,right]有序
	int begin1 = left, end1 = mid;
	int begin2 = mid + 1, end2 = right;
	int index = begin1;
	while (begin1 <= end1 && begin2 <= end2)
	{
		if (a[begin1] < a[begin2])
			tmp[index++] = a[begin1++];
		else
			tmp[index++] = a[begin2++];
	}

	while (begin1 <= end1)
		tmp[index++] = a[begin1++];

	while (begin2 <= end2)
		tmp[index++] = a[begin2++];

	//把归并好的在tmp中的数据再拷贝到原数组中
	for (int i = left; i <= right; ++i)
		a[i] = tmp[i];

	
}

2.3归并排序主函数

//归并排序递归实现
void MergeSort(int* a, int n)
{
	assert(a);
	int* tmp = malloc(sizeof(int) * n);

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

	free(tmp);
}

 2.2递归过程

2.3合并过程

2.4归并排序实现(递归版)

void _MergeSort(int* a, int left, int right, int*tmp)
{
	if (left >= right)
		return;
	
	int mid = (left + right) / 2;
	//[left,mid][mid+1,right]有序，则可以合并，现在无序，子问题解决
	_MergeSort(a, left, mid, tmp);
	_MergeSort(a, mid+1,right, tmp);

	//归并[left,mid][mid+1,right]有序
	int begin1 = left, end1 = mid;
	int begin2 = mid + 1, end2 = right;
	int index = begin1;
	while (begin1 <= end1 && begin2 <= end2)
	{
		if (a[begin1] < a[begin2])
			tmp[index++] = a[begin1++];
		else
			tmp[index++] = a[begin2++];
	}

	while (begin1 <= end1)
		tmp[index++] = a[begin1++];

	while (begin2 <= end2)
		tmp[index++] = a[begin2++];

	//把归并好的在tmp中的数据再拷贝到原数组中
	for (int i = left; i <= right; ++i)
		a[i] = tmp[i];

	
}


//归并排序递归实现
void MergeSort(int* a, int n)
{
	assert(a);
	int* tmp = malloc(sizeof(int) * n);

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

	free(tmp);
}

三.归并排序(非递归版本)

思路

使用成倍数增加的gap，不断调整需排序的区间，这里的gap按2倍递增

3.1(非递归版)图解

3.2一趟gap

通过控制原数组两个区间的起始位置，在tmp数组中进行这两个区间的排序与合并，这里的tmp是临时存储的最后把排序完的数组区间拷贝回原数组

 

void MergeArr(int* a, int begin1, int end1, int begin2, int end2, int* tmp)
{
	int left = begin1, right = end2;
	int index = begin1;
	while (begin1 <= end1 && begin2 <= end2)
	{
		if (a[begin1] < a[begin2])
			tmp[index++] = a[begin1++];
		else
			tmp[index++] = a[begin2++];
	}

	while (begin1 <= end1)
		tmp[index++] = a[begin1++];

	while (begin2 <= end2)
		tmp[index++] = a[begin2++];

	//把归并好的在tmp中的数据再拷贝到原数组中
	for (int i = left; i <= right; ++i)
		a[i] = tmp[i];
}

3.3多趟gap

注意：这里的尾区间有需要修正的情况，因为使用的gap会以2的倍数增大，当原数组元素个数不能被2整除时,就会出现问以下问题：

int gap = 1;
	while (gap < n)
	{
		for (int i = 0; i < n; i += 2 * gap)
		{
			//[i,i+gap-1][i+gap,i+2*gap-1]
			int begin1 = i, end1 = i + gap - 1;
			int begin2 = i + gap, end2 = i + 2 * gap - 1;
			//1.合并时只有一组，就不需要合并
			if (begin2 >= n)
				break;
			//2.合并时第二组只有部分数据，需要修正end2边界
			if (end2 >= n)
				end2 = n - 1;


			MergeArr(a, begin1, end1, begin2, end2, tmp);
		}
		PrintArry(a, n);
		gap *= 2;
	}

 

 3.4归并排序实现(非递归版)

void MergeArr(int* a, int begin1, int end1, int begin2, int end2, int* tmp)
{
	int left = begin1, right = end2;
	int index = begin1;
	while (begin1 <= end1 && begin2 <= end2)
	{
		if (a[begin1] < a[begin2])
			tmp[index++] = a[begin1++];
		else
			tmp[index++] = a[begin2++];
	}

	while (begin1 <= end1)
		tmp[index++] = a[begin1++];

	while (begin2 <= end2)
		tmp[index++] = a[begin2++];

	//把归并好的在tmp中的数据再拷贝到原数组中
	for (int i = left; i <= right; ++i)
		a[i] = tmp[i];
}



//归并排序非递归实现
void MergeSortNonR(int* a, int n)
{
	assert(a);
	int* tmp = malloc(sizeof(int) * n);
	int gap = 1;
	while (gap < n)
	{
		for (int i = 0; i < n; i += 2 * gap)
		{
			//[i,i+gap-1][i+gap,i+2*gap-1]
			int begin1 = i, end1 = i + gap - 1;
			int begin2 = i + gap, end2 = i + 2 * gap - 1;
			//1.合并时只有一组，就不需要合并
			if (begin2 >= n)
				break;
			//2.合并时第二组只有部分数据，需要修正end2边界
			if (end2 >= n)
				end2 = n - 1;


			MergeArr(a, begin1, end1, begin2, end2, tmp);
		}
		PrintArry(a, n);
		gap *= 2;
	}

	free(tmp);
}

四.全部代码

4.1全部代码

#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
void PrintArry(int* a, int n)
{
	for (int i = 0; i < n; ++i)
	{
		printf("%d ", a[i]);
	}
	printf("
");
}

//时间复杂度O(N*logN)
//空间复杂度O(N)
void _MergeSort(int* a, int left, int right, int* tmp)
{
	if (left >= right)
		return;

	int mid = (left + right) / 2;
	//[left,mid][mid+1,right]有序，则可以合并，现在无序，子问题解决
	_MergeSort(a, left, mid, tmp);
	_MergeSort(a, mid + 1, right, tmp);

	//归并[left,mid][mid+1,right]有序
	int begin1 = left, end1 = mid;
	int begin2 = mid + 1, end2 = right;
	int index = begin1;
	while (begin1 <= end1 && begin2 <= end2)
	{
		if (a[begin1] < a[begin2])
			tmp[index++] = a[begin1++];
		else
			tmp[index++] = a[begin2++];
	}

	while (begin1 <= end1)
		tmp[index++] = a[begin1++];

	while (begin2 <= end2)
		tmp[index++] = a[begin2++];

	//把归并好的在tmp中的数据再拷贝到原数组中
	for (int i = left; i <= right; ++i)
		a[i] = tmp[i];


}

void MergeArr(int* a, int begin1, int end1, int begin2, int end2, int* tmp)
{
	int left = begin1, right = end2;
	int index = begin1;
	while (begin1 <= end1 && begin2 <= end2)
	{
		if (a[begin1] < a[begin2])
			tmp[index++] = a[begin1++];
		else
			tmp[index++] = a[begin2++];
	}

	while (begin1 <= end1)
		tmp[index++] = a[begin1++];

	while (begin2 <= end2)
		tmp[index++] = a[begin2++];

	//把归并好的在tmp中的数据再拷贝到原数组中
	for (int i = left; i <= right; ++i)
		a[i] = tmp[i];
}


//归并排序非递归实现
void MergeSortNonR(int* a, int n)
{
	assert(a);
	int* tmp = malloc(sizeof(int) * n);
	int gap = 1;
	while (gap < n)
	{
		for (int i = 0; i < n; i += 2 * gap)
		{
			//[i,i+gap-1][i+gap,i+2*gap-1]
			int begin1 = i, end1 = i + gap - 1;
			int begin2 = i + gap, end2 = i + 2 * gap - 1;
			//1.合并时只有一组，就不需要合并
			if (begin2 >= n)
				break;
			//2.合并时第二组只有部分数据，需要修正end2边界
			if (end2 >= n)
				end2 = n - 1;


			MergeArr(a, begin1, end1, begin2, end2, tmp);
		}
		PrintArry(a, n);
		gap *= 2;
	}

	free(tmp);
}


//归并排序递归实现
void MergeSort(int* a, int n)
{
	assert(a);
	int* tmp = malloc(sizeof(int) * n);

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

	free(tmp);
}


void TestMergeSortNonR()
{
	printf("非递归版，归并排序：
");
	printf("原数组为：
");
	int a[] = { 2,4,5,3,9,8,0,5,1,44,6,0 };
	PrintArry(a, sizeof(a) / sizeof(a[0]));
	printf("非递归归并排序步骤:
");
	MergeSortNonR(a, sizeof(a) / sizeof(a[0]));
	printf("排序完成
");
	PrintArry(a, sizeof(a) / sizeof(a[0]));
	printf("


");
}

void TestMergeSort()
{
	printf("递归版，归并排序：
");
	printf("原数组为：
");
	int a[] = { 2,4,5,3,9,8,0,5,1,44,6,0 };
	PrintArry(a, sizeof(a) / sizeof(a[0]));
	MergeSort(a, sizeof(a) / sizeof(a[0]));
	printf("排序完成
");
	PrintArry(a, sizeof(a) / sizeof(a[0]));
}
int main()
{
	TestMergeSortNonR();
	TestMergeSort();
}

4.2运行结果截图

  以上就是本期内容，欢迎参考指正，如有不懂，欢迎评论或私信出下期！！！