【排序算法】—— 归并排序

        归并排序时间复杂度O(NlongN)，空间复杂度O(N)，是一种稳定的排序，其次可以用来做外排序算法，即对磁盘(文件)上的数据进行排序。

目录

一、有序数组排序

二、排序思路

三、递归实现

四、非递归实现

一、有序数组排序

要理解归并排序的核心逻辑我们得先看懂下面一个题：

         刚接触这个题的时候，大家可能会想把他俩写到一个数组里面然后再写一个排序算法，这是一个比较容易想到也是比较蛮力的一种方法，但是这里有一个特点这两个数组是有序的。所以有一个很巧妙的方法。

        使用两个变量分别记录他们的下标，并从零下标开始，比较他们下标对应下的值把小的那个先放进去新数组里面，然后把他的下标移到下一位。然后重复进行该操作，直到把其中的一个遍历完。

        当然此时还没有完全排完序，当其中一组遍历完后，还有另一组剩余的的元素没有放在新数组内，因为无法确定那一组会先遍历完所以我们俩组都需要检查一遍，检查他们的下标并把剩余元素放在新数组内。

#include
#include
#include
int main()
{
	int ar1[] = { 1,2,3,4 };
	int ar2[] = { 3,4,5,6,7 };
	int sz1 = sizeof(ar1)/sizeof(int), sz2 = sizeof(ar2) / sizeof(int);
	int* arr = (int*)malloc(sizeof(int) * (sz1 + sz2));
	assert(arr);
	int i = 0, j = 0, t = 0;
	while (i  
二、排序思路
 
        通过理解上面那个题，那么对于一个乱序的数组，我们可以把一分为二，先让两个小数组有序然后再用上面的方法合并。那么如何让这两个小数组有序呢，同样的可以把他们分别再拆开，变成四个小组，然后继续一直往下拆，直到拆到只有一个元素，那么它必然是有序的，最后进行进行一一合并，这整个的思路有点像二叉树的后续遍历。
 
 
动图：
 
 
三、递归实现
 
        在分析的过程中，我们就可以感受到使用递归可以很好的解决这个问题。在做分割的时候，最好是选择从中间位置开始，这样避免的递归深度太深。在处理递归问题的时候还要注意一个点，就是递归的结束条件，这里递归什么时候结束呢？通过上面的分析当数组只分割成单个元素的时候它必然是有序的，那么递归结束条件就是当分割的小数组只有一个元素的时候返回。
 
代码示例:
 
void _MergeSort(int* arr, int* tmp, int left, int right)
{
	if (left >= right)
		return;
	int key = (left + right) / 2;
	int begin1 = left, end1 = key;
	int begin2 = key + 1, end2 = right;
	_MergeSort(arr, tmp, begin1, end1);
	_MergeSort(arr, tmp, begin2, end2);
	int i = left;
	while (begin1