1、环境配置：
- 系统：win10
- 编程语言：C
- 编译器：DevC++
2、算法思想：
分治：先分，后治！
归并.png
注意：在“治”的阶段，需要有过一个新数组来存放合并数组，解释如下：
治的方法.png
- 递归的“分”容易理解，难点就是治。治就是借一个和原数组一样大的数组，把分开的两个部分，再合并起来。
- 伪代码：
int MergeSort(int A[],int B[],int low,int high)
{
//先“分”
int m;
if(low<high) then {
m=(low+high)/2;
MergeSort(A,low,m);//左边归并
MergeSort(A,m+1,heigh);//右边归并
int p=low;//左右合并
int q=m+1;
int t=low;//这里很关键
while((p<=m)&&(q<=heigh)) do{
if(A[p]<A[q]) then{
B[t]=A[p];
t=t+1;
p=p+1;
}
if(A[p]>A[q]) then{
B[t]=A[q];
t=t+1;
q=q+1;
}
}
while(p<=m) do{
B[t]=A[p];
t=t+1;
p=p+1;
}
while(q<=heigh) do{
B[t]=A[q];
t=t+1;
q=q+1;
}
for(i=0 to heigh){//将数组B返回给数组A
A[i]=B[i];
}
}
return 0;
}
3、代码：
#include<stdio.h>
#include<stdlib.h>
int MergeSort(int sourceArr[], int tempArr[], int low, int high);
int main()
{
int a[]={1,3,2,7,6};
int b[5];
for (int i = 0; i < 5; i++)
printf("%d ", a[i]);
printf("\n");
MergeSort(a, b, 0, 4);
for (int i = 0; i < 5; i++)
printf("%d ", b[i]);
return 0;
}
int MergeSort(int sourceArr[], int tempArr[], int low, int high)
{
int mid;
if(low < high)
{
mid = (low + high) / 2;
MergeSort(sourceArr, tempArr, low, mid);//左边归并
MergeSort(sourceArr, tempArr, mid + 1, high);//右边归并
// Merge(tempArr, sourceArr, low, mid, high);
int i = low, j = mid + 1, k = low;//借用第三个数组，左右合并。
while(i <= mid && j <= high)
{
if(sourceArr[i] < sourceArr[j])
{
tempArr[k] = sourceArr[i];
k=k+1;
i=i+1;
}
else
{
tempArr[k] = sourceArr[j];
k=k+1;
j=j+1;
}
}
while(i <= mid)
{
tempArr[k] = sourceArr[i];
k=k+1;
i=i+1;
}
while(j <= high)
{
tempArr[k] = sourceArr[j];
k=k+1;
j=j+1;
}
//最后再把tempArr中的值给sourceArr赋值填回去。
for (int p = low; p <= high; p++)
sourceArr[p] = tempArr[p];
}
return 0;
}
4、结果展示：
1.png
5、反思总结：
- 归并函数思考相对比较复杂，可以先从逻辑上捋顺它：
1、先左边归并；
2、再右边归并；
3、最后左和右借助第三个数组来合并； - 然后我们采用极限思维，手动执行一次一个比较小的数组｛4，3，2｝的归并排序
/*
为了验证手写稿的正确性，我给代码当中关键位置设置了打印语句。
*/
#include<stdio.h>
#include<stdlib.h>
int MergeSort(int sourceArr[], int tempArr[], int low, int high);
int main()
{
int a[]={4,3,2};
int b[3];
for (int i = 0; i < 3; i++)
printf("%d ", a[i]);
printf("\n");
MergeSort(a, b, 0, 2);
for (int i = 0; i < 3; i++)
printf("%d ", a[i]);
return 0;
}
int MergeSort(int sourceArr[], int tempArr[], int low, int high)
{
int mid;
if(low < high)
{
mid = (low + high) / 2;
printf("开始mid:%d\n",mid);
MergeSort(sourceArr, tempArr, low, mid);//左边归并
printf("左边结束mid：%d\n",mid);
MergeSort(sourceArr, tempArr, mid + 1, high);//右边归并
printf("右边结束mid：%d\n",mid);
int i = low, j = mid + 1, k = low;//借用第三个数组，左右合并。
while(i <= mid && j <= high)
{
if(sourceArr[i] < sourceArr[j])
{
tempArr[k] = sourceArr[i];
k=k+1;
i=i+1;
}
else
{
tempArr[k] = sourceArr[j];
k=k+1;
j=j+1;
}
}
while(i <= mid)
{
tempArr[k] = sourceArr[i];
k=k+1;
i=i+1;
}
while(j <= high)
{
tempArr[k] = sourceArr[j];
k=k+1;
j=j+1;
}
//最后再把tempArr中的值给sourceArr赋值填回去。
for (int p = low; p <= high; p++)
sourceArr[p] = tempArr[p];
}
return 0;
}
结果：
实验.png
手写验证（自己的思维过一遍）：
归并排序验证.jpg
- 总结：其实这种归并排序递归程序比较难的地方就是把递归调用放在了递归程序中间，这种递归问题就要在逻辑上把握清楚。在代码实现的时候，要注意传输值的重要性，就比如这个归并代码中，后面部分的k=low，而不是k=0。
