数据结构归并排序

目录

前世今生

实际应用

核心思想

递归法代码

动图演示

 全部代码

前世今生

1945年，约翰·冯·诺依曼（John von Neumann）发明了归并排序，这是典型的分治算法的应用。

距今已有差不多80年。

实际应用

你们知道高考一本，二本，专科分数线是如何划分的呢？

假设各个高校本科专业在全省招生一万人，那么只需要将分数到排序，第一万名就是那一年的本科分数线。即使你是你们班级第一，甚至是年级第一。只要你没有上分数线，就是没有到全省一万名，你也就失去了上本科的机会。

这一万人当中可以细分为：每个市，每个县，每个学校，每个班级的排名合并之后再合并的结果。即就是先把每个班级的分数排好序，每个学校的分数排好序，每个县的分数排好序，每个市的分数·排好序，最后再把这些已经有序的数据合并到一起就是这一万人的排名。

核心思想

假设有一个长度为n的数组，我们可以看成是n个有序的数列，每个子序列长度为1，然后两两归并。

相当于n一直除2，直到不能除了为止，就是一个序列里面只有一个数了，就是不能再分了。

分完之后开始合，也是每次乘2的合，直到不能再合为止，就是长度为n的序列已经有序了。

递归法代码

void _Merge(int* a, int left, int right, int* tmp)
{
	if (left >= right)//递归结束条件
		return;
	int mid = (left + right) / 2;
	//[left , mid] [mid+1, right] 有序则可以合并，现在它们没有序，子问题解决
	_Merge(a, left, mid, tmp);//对左区间进行递归
	_Merge(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++];
	}
	//前面循环结束还有数据没放入tmp中，继续放
	while (begin1 <=end1)
		tmp[index++] = a[begin1++];
	//前面循环结束还有数据没放入tmp中，继续放
	while (begin2 <= end2)
		tmp[index++] = a[begin2++];

	//把归并好的数据，拷贝回原空间
	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);

	//函数调用
	_Merge(a, 0, n - 1, tmp);

	free(tmp);//销毁空间
}

动图演示

递归图

 全部代码

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
void _Merge(int* a, int left, int right, int* tmp)
{
	if (left >= right)//递归结束条件
		return;
	int mid = (left + right) / 2;
	//[left , mid] [mid+1, right] 有序则可以合并，现在它们没有序，子问题解决
	_Merge(a, left, mid, tmp);//对左区间进行递归
	_Merge(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++];
	}
	//前面循环结束还有数据没放入tmp中，继续放
	while (begin1 <= end1)
		tmp[index++] = a[begin1++];
	//前面循环结束还有数据没放入tmp中，继续放
	while (begin2 <= end2)
		tmp[index++] = a[begin2++];

	//把归并好的数据，拷贝回原空间
	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);

	//函数调用
	_Merge(a, 0, n - 1, tmp);

	free(tmp);//销毁空间
}

int main()
{
	int arr[] = { 14,12,15,13,11,16 };
	for (int i = 0; i < 6; i++)
	{
		printf("%d ", arr[i]);
	}printf("\n");
	MergeSort(arr, sizeof(arr) / sizeof(arr[0]));
	for (int i = 0; i < 6; i++)
	{
		printf("%d ", arr[i]);
	}
	return 0;
}