数组归并排序

（声明：文章全部图片均来自 传智播客 教师课件）归并排序是一种空间换时间的做法，排序的速度当然会提高很多，归并排序中会产生一个临时数组，这个临时数组用来把不断拆分到最后的有序数据进行合并，最后再把合并后的数据重新赋值给原数组，这样就实现了排序。主要分为以下三个步骤：

1、把原数组无限拆分到最少元素（直至剩余一个）如下图表示：

2、把拆分的两组数据合并到临时数组，如下图表示：

3、最后把临时数组中的值覆盖掉原始数组的值，整个过程就是下图这样的：

【实现代码】

#include <stdio.h>

void mergeArray(int arr[], int first, int mid, int last, int temp[])
{
	// 两个有序序列合并后的长度
	int length = 0;
	// 记录拆分后左侧起始下标
	int i = first;
	// 记录拆分后右侧起始下标
	int j = mid + 1;

	// 判断两个有序序列的下标是否到最后一个元素了
	while (i <= mid && j <= last)
	{
		// 判断值哪个值小
		if (arr[i] <= arr[j])
		{
			// 把小的值放到 temp 临时数组中
			temp[length] = arr[i];
			// 把小的数组的值下标向后移动
			i++;
		}
		else
		{
			// 同上
			temp[length] = arr[j];
			j++;
		}
		// 每放进去一个值，记录temp数组长度的下标值就要+1
		length++;
	}

	// 当上面循环结束时，一定还有一个数组没有遍历完，一个已经全部遍历完了
	// 我们要把那个没有遍历完的数据剩下的元素放到临时数组中
	while (i <= mid)
	{
		// 如果i的下标还没到最最后的位置，那么就循环把值赋给临时数组
		temp[length] = arr[i];
		length++;
		i++;
	}
	while (j <= mid)
	{
		// 如果j的下标还没到最最后的位置，那么就循环把值赋给临时数组
		temp[length] = arr[j];
		length++;
		j++;
	}

	for (i = 0; i < length; i++)
	{
		// 有可能是从数组的中间位置开始拷贝的，这取决于传递进函数的参数
		arr[first + i] = temp[i];
	}
}

void mergeSort(int arr[], int first, int last, int temp[])
{
	if (first < last)
	{
		// 将数据分割成两份
		int mid = (first + last) / 2;
		// 一次递归把两份左侧的数据和右侧的数据再次拆分
		mergeSort(arr, first, mid, temp);
		mergeSort(arr, mid + 1, last, temp);
		// 把拆分的数据进行排序（递归中，是从拆分到最后的2个或3个数进行排序）
		mergeArray(arr, first, mid, last, temp);
	}
}

int main(int argc, char* argv[])
{
	int arr[11] = { 1, 21, 91, 284, 74, 57, 10, 38, 292, 28, 71 };
	int temp[11];
	
	mergeSort(arr, 0, 11 - 1, temp);

	for (int i = 0; i < 11 - 1; i++)
	{
		printf("%d ", arr[i]);
	}
	
	return 0;
}