排序算法7----归并排序（C语言）

? ? ? ? 1、基本思想

? ? ? ? 归并排序是建立在归并操作上的一种有效的排序算法，该算法是采用分治法的一个非常典型的应用。

? ? ? ? 将无序的序列分解到单个元素，然后将有序的子序列合并，得到完全有序的序列：即先使每个子序列有序，再使子序列段间有序。

? ? ? ? 若将两个有序表合并成一个有序表，称为二路归并。

? ? ? ? 2、核心步骤

? ? ? ? 3、代码实现

? ? ? ? ?3、1主要核心代码

void SubMergeSort(int* arr, int begin, int end, int* tmp)
{
	//分解
	//将arr数组分成n个单个元素

	//分解结束条件：begin>=end，即已经分解到单个元素
	if (begin >= end)
		return;

	//从每个区间的中间开始分,每次分解会将一个区间分解为两个区间
	int mid = (begin + end) / 2;
	//递归分解
	SubMergeSort(arr, begin, mid, tmp);
	SubMergeSort(arr, mid + 1, end, tmp);


	//合并
	//因为一个区间分解后得到两个区间，先定义这两个区间的始末位置
	int begin1 = begin, end1 = mid;
	int begin2 = mid + 1, end2 = end;

	//定义每两个有序子序列放入tmp数组中的下标i
	//这个begin是这两个相邻有序子序列分解前的区间的begin
	int i = begin;

	//将两个有序子序列放入tmp
	//一个元素也叫有序
	while (begin1 <= end1 && begin2 <= end2)
	{
		//由于两个子序列已经有序，故我们只需要从两个子序列的起始处开始比较
		if (arr[begin1] < arr[begin2])
			tmp[i++] = arr[begin1++];
		else
			tmp[i++] = arr[begin2++];
	}

	//while结束时，代表其中的一个begin已经大于end了
	//代表有一个子序列已经全部放入tmp
	//接下来只需要将另一个子序列剩下的元素放入tmp
	while (begin1 <= end1)//代表第二个子序列已经放完，现在放第一个
	{
		tmp[i++] = arr[begin1++];
	}
	while (begin2 <= end2)
	{
		tmp[i++] = arr[begin2++];
	}
	
	//到这，两个有序子序列已经合并到一个有序序列
	//将这个有序序列在tmp中对应位置，拷贝回到arr中对应位置
	//这样下次才能从arr中再次将两个有序子序列再合并为一个有序序列放入tmp中
	//当已经将arr的最后两个有序子序列合并到tmp中后，tmp已经有序，再拷贝回去，arr就有序

	memcpy(arr + begin, tmp + begin, sizeof(int) * (end - begin + 1));//这里+begin，就是对应上边第二点的对应位置
	//从哪个区间分解出来，就放回哪个区间
}

? ? ? ? 3、2辅助代码

void MergeSort_incline(int* arr, int n)
{
	//建立tmp数组来重新排序，排序完成后将tmp拷贝给arr
	int* tmp = (int*)malloc(sizeof(int) * n);
	if (tmp == NULL)
	{
		perror("malloc fail\n");
		exit(-1);
	}
	SubMergeSort(arr, 0, n - 1, tmp);
	free(tmp);
	tmp = NULL;
}

? ? ? ? 4、实现效果

	int arr[] = { 3,4,8,10,1,7,1,5,2,8,2 };
	int n = sizeof(arr) / sizeof(int);
	printf("原数组： ");
	PrintArray(arr, n);
	printf("\n");

	printf("排序后： ");
	MergeSort_incline(arr, n);
	PrintArray(arr, n);