【数据结构】八大排序之归并排序算法

修修修也

发布于 2024-04-01 16:12:05

750

发布于 2024-04-01 16:12:05

一.归并排序简介及思想

"归并"一词的中文含义就是合并,并入的意思,而在数据结构中的定义是将两个或两个以上的有序表组合成一个新的有序表.
归并排序(Merging Sort)就是利用归并的思想实现的排序方法. 它的原理是: 假设初始序列含有n个记录,则可看成是n个有序的子序列,每个子序列的长度为1,然后两两归并,得到

(

表示不小于x的最小整数)个长度为2或1的有序子序列;再两两归并,......,如此重复,直至得到一个长度为n的有序序列为止,这种排序方法称为2路归并排序.

算法动图演示如下:

算法逻辑演示:

二.归并排序的代码实现

算法实现步骤:(以升序为例)

将数组中的n个数据看成n个有序子序列
然后将其两两归并到新数组内,得到

+1或

个长度为1或2的有序子序列,将新数组的数据拷贝回原数组.

重复步骤2,直到归并得到一个长度为n的有序序列为止.

综上,归并排序的代码实现如下:

//归并递归子函数
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 = 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++];
	}

	//拷贝tmp回原数组
	memcpy(a + begin, tmp + begin, sizeof(int) * (end - begin + 1));

}

//归并排序
void MergeSort(int* a, int n)//不写区间,因为该函数不递归自己,否则每次都要malloc
{
	//开数组
	int* tmp = (int*)malloc(sizeof(int) * n);
	if (tmp == NULL)
	{
		perror("malloc fail::\n");
		return;
	}

	_MergeSort(a, 0, n - 1, tmp);//归并递归子函数

	free(tmp);
}

三.归并排序的非递归代码实现

算法实现思路:(以升序为例) 因为归并排序递归是将完整的数组不断分割成只有一个元素的数组进行归并的,那么我们实现非递归的时候,就可以在一开始直接将数组视为n个只有一个元素的子序列进行归并,然后再按照两个两个元素的数组进行归并,一直向上归并,直到归并成为一个有n个元素的有序数组为止. 归并排序在非递归实现时需要额外注意当n不是2的次方倍时归并数组末尾的越界现象,并对此错误现象做出及时的修正.

归并排序的非递归实现代码如下:

//归并排序非递归
void MergeSortNonR(int* a, int n)
{
	//开数组
	int* tmp = (int*)malloc(sizeof(int) * n);
	if (tmp == NULL)
	{
		perror("malloc fail::\n");
		return;
	}

	int gap = 1;

	while (gap < n)
	{
		for (int i = 0; i < n; i =i+ 2 * gap)
		{
			int begin1 = i, end1 = i + gap - 1;
			int begin2 = i + gap, end2 = i + 2 * gap - 1;

			//修正数组非2的次方倍数时的越界现象
			if (end1 >= n)
			{
				end1 = n - 1;
				begin2 = n;
				end2 = n - 1;
			}
			else if (begin2 >= n)
			{
				begin2 = n;
				end2 = n - 1;
			}
			else if (end2 >= n)
			{
				end2 = n - 1;
			}

			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++];
			}
		}
		memcpy(a, tmp, sizeof(int) * n);
		gap *= 2;
	}

	free(tmp);
}