🎉个人名片：
🐼作者简介：一名乐于分享在学习道路上收获的大二在校生
🐻❄个人主页🎉：GOTXX
🐼个人WeChat：ILXOXVJE
🐼本文由GOTXX原创，首发CSDN🎉🎉🎉
🕊系列专栏：零基础学习C语言----- 数据结构的学习之路
🐓每日一句：如果没有特别幸运，那就请特别努力！🎉🎉🎉
————————
🎉文章简介：
本篇文章对 归并排序 的相关知识详细讲解！
如果您觉得文章不错，期待你的一键三连哦，你的鼓励是我创作动力的源泉，让我们一起加油，一起奔跑，让我们顶峰相见！！！🎉🎉🎉
目录
归并排序
基本思想
图解
代码实现（代码中含分析）
递归实现：
非递归实现：
性能分析
归并排序
基本思想
归并思想：
将两个有序数组归并到一起，使其有序；
两个数组中取小尾插到新数组；
归并排序的基本思想：
1.一组数据想要有序，可以先使其左半部分有序，右半部分有序，再利用归并的思想使其整体有序；
2.在将左边的数据变为有序时，又可以分为两部分，先使其左边有序，右边有序，再利用归并想使其整体有序；
3.利用上述思想，将待排数据分为两部分，直到分到每组数据只有一个时，再边排序边返回；
4.这里归并时，需要用到另一个数组，将原数组的数据归并到该数组使其有序，再将数据拷贝回原数组；
图解
代码实现（代码中含分析）
递归实现：
void _MergeSort(int* a, int* tmp ,int begin, int end)
{
if (begin >= end)
return;
int mid = (begin + end) / 2;
//[begin,mid][mid+1,end]
_MergeSort(a, tmp, begin, mid);
_MergeSort(a, tmp, mid+1,end);
//递归到tmp数组
//[begin1,end1][begin2,end2]
int begin1 = begin, end1 = mid;
int begin2 = mid+1, end2 = end;
int i = begin;
while (begin1<=end1 && begin2<=end2)
{
//取小的尾插到tmp数组
if (a[begin1] <= a[begin2])
tmp[i++] = a[begin1++];
else
tmp[i++] = a[begin2++];
}
//退出循环，有一个区间的元素还未取完
//因为两区间的数据都在本区间已经有序，所以剩余数据直接插入
while (begin2 <= end2)
{
tmp[i++] = a[begin2++];
}
while (begin1 <= end1)
{
tmp[i++] = a[begin1++];
}
//递归完一次后将tmp中数据拷贝回原数组
//注意拷贝回去时，注意拷贝回原位置
memcpy(a+begin, tmp+begin, sizeof(int)*(end-begin+1));
}
void MergeSort(int* a ,int begin, int end)
{
//开辟一个与待排数组同大小的tmp数组，用于归并
int* tmp = (int* )malloc(sizeof(int) * (end - begin + 1));
if (tmp == NULL)
{
perror("malloc fail");
return;
}
_MergeSort(a,tmp, begin, end);
free(tmp);
}
非递归实现：
void MergeSortNonR(int* a, int n)
{
int* tmp = (int*)malloc(sizeof(int) * n);
if (tmp == NULL)
{
perror("malloc fail");
return;
}
//gap等于几就是几个和几个进行归并，不一定是均分
int gap = 1;
while (gap < n)
{
//用i控制区间边界，i+=2*gap时，就进行同层的后组归并
for (int i = 0; i <n; i += 2*gap)
{
int begin1 = i, end1 = i + gap-1;
int begin2 = i + gap, end2 =i + 2*gap-1;
//越界处理，如果end1越界，或则begin2越界，那么第二个区间不存在，就不需要归并
if (end1 > n || begin2 >= n)
{
return;
}
//如果只是end2越界了，只需要修改边界
if (end2 > n)
{
end2 = n-1;
}
//tmp数组的下标
//开始归并
int cur = i;
while (begin1 <= end1 && begin2 <= end2)
{
if (a[begin1] < a[begin2])
tmp[cur++] = a[begin1++];
else
tmp[cur++] = a[begin2++];
}
while (begin2 <= end2)
{
tmp[cur++] = a[begin2++];
}
while (begin1 <= end1)
{
tmp[cur++] = a[begin1++];
}
//拷贝回原数组
memcpy(a + i, tmp + i, sizeof(int)*(end2-i+1));
}
//一一归完两两归，两两归完四四归……
gap *= 2;
}
free(tmp);
}性能分析
时间复杂度：O(N*logN)
空间复杂度:O(N)
稳定性：稳定
