29.归并排序

研究了这么多算法以后，小桂子颇有收获，基本自认为排序算法已经全部掌握，于是就想卖弄一下自己的“算法内功”，另一方面为了交流推广，把这些算法传播出去，就召开一个全国算法大赛，集思广益，征集更牛逼的算法！
在算法大赛上，有两位白发葱葱的老者提出的算法让小桂子自惭形秽，感叹良多。。。

其中一位叫归并长老的老者，提出了如下的排序方法：

当两个组数据已经有序，我们可以通过如下方式（以下简称归并大法）让两组数据快速有序

我们可以依次从两组中取最前面的那个最小元素依次有序放到新的数组中，然后再把新数组中有序的数据拷贝到原数组中，快速完成排序。

依靠这种思想，归并长老提出了如下的排序方法！

具体步骤
对于下面这一组待排序的数组

先以中间为界，把其均分为A 和B 两个数组（如果是奇数个，允许两组数相差一个）

如果A 和B 两组数据能够有序，则我们可以通过上面的方式让数组快速排好序。

此时，A 组有4 个成员，B 组有5个成员，但两个数组都无序，然后我们可以采用分治法继续对A组和B组进行均分，以A 组为例，又可以均分A1和A2两个组如下：

均分后，A1组和A2组仍然无序，继续利用分治法细分，以A1组为例，A1又可分成如下两组

数组细分到一个元素后，这时候，我们就可以采用归并法借助一个临时数组将数组A1 有序化！A2 同理！

依次类推，将A1组和A2组归并成有序的A组， B 组同理！

最后，将A和B组使用归并大法合并，就得到了完整的有序的结果！

代码实现:

1.数组前后两部分均有序排列

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

void mergeAdd_demo(int arr[], int left, int mid, int right)
{
	int temp[64] = { 0 };

	int i = left;//指向左边数组最小的元素位置
	int j = mid;//指向右边数组最小的元素位置
	int k = 0;//临时数组的下标

	while (i < mid && j <= right)
	{
		if (arr[i] < arr[j])
		{
			temp[k++] = arr[i++];
		}
		else
		{
			temp[k++] = arr[j++];
		}
	}

	while (i < mid)
	{
		temp[k++] = arr[i++];
	}
	while (j <= right)
	{
		temp[k++] = arr[j++];
	}

	//把temp中的内容拷贝到arr数组中
	memcpy(arr + left, temp,  sizeof(int)*(right - left + 1));
}

int main()
{
	int beauties[] = { 1, 3, 6, 7, 2, 4, 5, 8};

	int len = sizeof(beauties) / sizeof(beauties[0]);

	int mid = len / 2;

	mergeAdd(beauties, 0,  mid, len - 1);

	printf("执行归并大法后:\n");
	for (int i = 0; i < len; i++)
	{
		printf("%d ", beauties[i]);
	}

	system("pause");
	return 0;
}

2.数组前后两部分无序排列

void mergeAdd(int arr[], int left, int mid, int right, int *temp)
{
	//int temp[64] = { 0 };

	int i = left;//指向左边数组最小的元素位置
	int j = mid;//指向右边数组最小的元素位置
	int k = left;//临时数组的下标

	while (i < mid && j <= right)
	{
		if (arr[i] < arr[j])
		{
			temp[k++] = arr[i++];
		}
		else
		{
			temp[k++] = arr[j++];
		}
	}

	while (i < mid)
	{
		temp[k++] = arr[i++];
	}
	while (j <= right)
	{
		temp[k++] = arr[j++];
	}

	//把temp中的内容拷贝到arr数组中
	memcpy(arr + left, temp + left, sizeof(int) * (right - left + 1));
}

void mergeSort(int arr[], int left, int right, int* temp)//归并排序
{
	int mid = 0;

	if (left < right)
	{
		mid = left + (right - left) / 2;
		mergeSort(arr, left, mid, temp);
		mergeSort(arr, mid + 1, right, temp);
		mergeAdd(arr, left, mid + 1, right, temp);
	}
}

int main()	
{
	int beauties[] = { 10, 11, 12, 13, 2, 4, 5, 8};

	int len = sizeof(beauties) / sizeof(beauties[0]);

	int* temp = new int[len];

	int mid = len / 2;

	mergeSort(beauties, 0, len - 1, temp);
	//mergeAdd(beauties, 0,  mid, len - 1, temp);

	printf("执行归并大法后:\n");
	for (int i = 0; i < len; i++)
	{
		printf("%d ", beauties[i]);
	}

	system("pause");
	return 0;
}

参考资料来源：

奇牛学院