归并排序时间复杂度O(NlongN)，空间复杂度O(N)，是一种稳定的排序，其次可以用来做外排序算法，即对磁盘(文件)上的数据进行排序。
一、有序数组排序要理解归并排序的核心逻辑我们得先看懂下面一个题：
刚接触这个题的时候，大家可能会想把他俩写到一个数组里面然后再写一个排序算法，这是一个比较容易想到也是比较蛮力的一种方法，但是这里有一个特点这两个数组是有序的。所以有一个很巧妙的方法。
使用两个变量分别记录他们的下标，并从零下标开始，比较他们下标对应下的值把小的那个先放进去新数组里面，然后把他的下标移到下一位。然后重复进行该操作，直到把其中的一个遍历完。
当然此时还没有完全排完序，当其中一组遍历完后，还有另一组剩余的的元素没有放在新数组内，因为无法确定那一组会先遍历完所以我们俩组都需要检查一遍，检查他们的下标并把剩余元素放在新数组内。
代码语言：javascript复制#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 < sz1 && j < sz2)
{
if (ar1[i] < ar2[j])
arr[t++] = ar1[i++];
else
arr[t++] = ar2[j++];
}
while (i < sz1)
arr[t++] = ar1[i++];
while (j < sz2)
arr[t++] = ar2[j++];
for (int i = 0; i < sz1 + sz2; i++)
printf("%d ", arr[i]);
return 0;
}二、排序思路 通过理解上面那个题，那么对于一个乱序的数组，我们可以把一分为二，先让两个小数组有序然后再用上面的方法合并。那么如何让这两个小数组有序呢，同样的可以把它们分别再拆开，变成四个小组，然后继续一直往下拆，直到拆到只有一个元素，那么它必然是有序的，最后进行一一合并，这整个的思路有点像二叉树的后续遍历。
动图：
三、递归实现 在分析的过程中，我们就可以感受到使用递归可以很好的解决这个问题。在做分割的时候，最好是选择从中间位置开始，这样避免的递归深度太深。在处理递归问题的时候还要注意一个点，就是递归的结束条件，这里递归什么时候结束呢？通过上面的分析当数组只分割成单个元素的时候它必然是有序的，那么递归结束条件就是当分割的小数组只有一个元素的时候返回。
代码示例:
代码语言：javascript复制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 <= end1 && begin2 <= end2)
{
if (arr[begin1] < arr[begin2])
tmp[i++] = arr[begin1++];
else
tmp[i++] = arr[begin2++];
}
while (begin1 <= end1)
tmp[i++] = arr[begin1++];
while (begin2 <= end2)
tmp[i++] = arr[begin2++];
memcpy(arr + left, tmp + left, sizeof(int) * (right - left + 1));
}
void MergeSort(int* arr, int size)//归并排序——递归
{
int* tmp = (int*)malloc(sizeof(int) * size);
assert(tmp);
_MergeSort(arr, tmp, 0, size - 1);
free(tmp);
}四、非递归实现 把递归转为非递归可以防止函数栈针开的太多导致栈溢出。在把递归转为非递归时第一想到的应该是使用栈结构来辅助完成。但是对于这个排序使用栈来实现非递归还是比较复杂，也根本用不着。
思路：
gap：表示分割的每个小数组中储存的元素个数。
size：表示整个大数的长度
首先我们仿照广度优先的思想去合并，因为刚开始只有单个元素自己作为一个数组(即gap=1)的时候才有序，所以从最后一层开始两两合并成一个，那么接下来gap=2的小数组就变得有序，合并完gap=2的的数组后，同理gap=4的小数组变得有序，对它们进行两两合并，直到gap>=size。
代码示例:
代码语言：javascript复制void MergeSortNoF(int* arr, int sz)
{
int* tmp = (int*)malloc(sizeof(int) * sz);
assert(tmp);
int gap = 1;
while (gap < sz)
{
for (int i = 0; i < sz; i += gap * 2)
{
int j = i;
int begin1 = i, end1 = i + gap - 1;
int begin2 = i + gap, end2 = i + 2 * gap - 1;
if (begin2 >= sz)
break;
if (end2 >= sz)
end2 = sz - 1;
while (begin1 <= end1 && begin2 <= end2)
{
if (arr[begin1] <= arr[begin2])
tmp[j++] = arr[begin1++];
else
tmp[j++] = arr[begin2++];
}
while (begin1 <= end1)
tmp[j++] = arr[begin1++];
while (begin2 <= end2)
tmp[j++] = arr[begin2++];
memmove(arr + i, tmp + i, sizeof(int) * (end2 - i + 1));
}
gap*=2;
}
}细节：
无论是递归还是非递归都需要开辟一块空间tmp来储存合并后的元素，最后把tmp上的数据拷贝给原数组，使用memmove函数比较便捷。
区间越界问题：
(1)、[begin1, end1] [begin2, end2]
(2)、[begin1, end1] [begin2, end2]
(3)、[begin1, end1] [begin2, end2]
以上红色表示越界，这是越界可能出现的所有情况，观察发现出现(2)，(3)种情况的时候并不需要做合并，直接break;怎么写条件呢？因为end1越界begin2一定越界，所有用一个if(begin2>=sz)就可以表示(2)，(3)种情况。
至于第一种情况，我们还是要合并的但需要调整end2为sz-1，所以有一下代码：
评论留言