数据结构 ——— 归并排序算法的实现

归并排序的思想

归并排序算法的实现

归并排序的思想

将已经有序的子序列合并，得到完全有序的序列，即先使每个子序列有序后，再使子序列段间有序
若将两个有序表合并成一个有序表，称为二路归并

归并排序步骤示意图：

由此可以看出归并排序是需要递归分治解决的，把原数组分治成各个子序列，要先让各个子序列有序，最后才能让整个数组有序

让子序列有序的步骤是：取小的尾插

举例说明：

走到最后一步时，有两个子序列：[1,6,7,10] 和 [2,3,4,9]

这两个子序列都被分解归并为有序了，只要将这两个子序列再次归并，就能有序

所以需要两个指针，指向这两个子序列的开头，找到比较小的那个值，进行尾插

那么尾插就不能在原数组上尾插，因为会覆盖数据

所以要在最开始定义一个和待排序的数据等长的 tmp 数组，来进行尾插

最后再把 tmp 数组中的内容拷贝到原数组，这样，原数组才算完成了排序

归并排序算法的实现

代码演示：

static void _MergeSort(int* tmp, int* a, int begin, int end)
{
	/*结束条件*/ 
	if (begin == end)
		return;

	/*分解*/ 
	int mid = (begin + end) / 2;
	
	// [begin,mid] [mid+1,end]
	
	_MergeSort(tmp, a, begin, mid);
	_MergeSort(tmp, a, mid + 1, end);

	/*归并*/
	// 第一段子区间
	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++];
		}
	}

	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 size)
{
	int* tmp = (int*)malloc(sizeof(int) * size);

	// 判断是否开辟成功
	if (tmp == NULL)
	{
		perror("malloc fail");
		return;
	}

	// 归并排序子函数
	_MergeSort(tmp, a, 0, size - 1);

	free(tmp);
}

代码解析：

MergeSort 函数用来接收指向待排序数组首元素的指针，和数组长度

要利用 tmp 数组来接收数组 a 排好后的数据

所以不能直接利用 MergeSort 函数来递归，否则每次递归都会定义一个 tmp 函数

在 MergeSort 函数中再定义一个子函数 _MergeSort 函数，利用 _MergeSort 函数递归完成归并排序

由归并排序的思想得出，要先找出中间值，分割成两个子序列

也就是 [begin,mid] [mid+1,end] 这两个区间

所以可以得出递归的结束条件是当区间只有一个值时，就返回

当 begin == end 时，说明此时区间只有一个值

再利用 _MergeSort 函数进行递归两个子序列

然后再归并两个子序列，第一个 while 循环是把序列中小的值尾插到 tmp 中，第二、三个 while 循环是把没有走完的那个序列直接尾插到 tmp 数组后面

最后再将 tmp 数组内的有效数据个数拷贝到 a 数组相对应的位置