UC知道c语言归并排序简单问题
来源：百度知道 编辑：UC知道 时间：2024/05/28 18:09:34
以下是<<C语言实例解析精粹>>(第二版)上归并排序源程序，比较简单。
我的问题是void Merge_SortDC函数中调用自己递归嵌套的执行顺序，希望说得我明白。谢谢！ 程序已简化。
/* 归并排序 */
#include <stdio.h>
#define MAX 255
int R[MAX];
void Merge(int low,int m,int high)
{/* 将两个有序的子文件R[low..m)和R[m+1..high]归并成一个有序的 */
/* 子文件R[low..high] */
...
}
void Merge_SortDC(int low,int high)
{/* 用分治法对R[low..high]进行二路归并排序 */
int mid;
if(low<high)
{/* 区间长度大于1 */
mid=(low+high)/2; /* 分解 */
Merge_SortDC(low,mid); /* 递归地对R[low..mid]排序 */
Merge_SortDC(mid+1,high); /* 递归地对R[mid+1..high]排序 */
Merge(low,mid,high); /* 组合，将两个有序区归并为一个有序区 */
}
}
void main()
{
int i,n;
clrscr();
...
Merge_SortDC(1,n);
...
puts("\n Press any key to quit...");
getch();
}
比如n=8,那么Merge_SortDC()的执行步骤，它其中的Merge(int low,int m,int high) 又是什么时候执行？
我的问题是void Merge_SortDC函数中调用自己递归嵌套的执行顺序，希望说得我明白。谢谢！ 程序已简化。
/* 归并排序 */
#include <stdio.h>
#define MAX 255
int R[MAX];
void Merge(int low,int m,int high)
{/* 将两个有序的子文件R[low..m)和R[m+1..high]归并成一个有序的 */
/* 子文件R[low..high] */
...
}
void Merge_SortDC(int low,int high)
{/* 用分治法对R[low..high]进行二路归并排序 */
int mid;
if(low<high)
{/* 区间长度大于1 */
mid=(low+high)/2; /* 分解 */
Merge_SortDC(low,mid); /* 递归地对R[low..mid]排序 */
Merge_SortDC(mid+1,high); /* 递归地对R[mid+1..high]排序 */
Merge(low,mid,high); /* 组合，将两个有序区归并为一个有序区 */
}
}
void main()
{
int i,n;
clrscr();
...
Merge_SortDC(1,n);
...
puts("\n Press any key to quit...");
getch();
}
比如n=8,那么Merge_SortDC()的执行步骤，它其中的Merge(int low,int m,int high) 又是什么时候执行？
当调用Merge_SortDC(1,8);时，
Merge_SortDC(1,4); 与Merge_SortDC(4+1,8); 都执行成功返回以后
两边的数组都是有序的了，这时候，执行Merge(low,mid,high)，也就是Merge(1,4,8）。
至于Merge_SortDC(1,4); 与Merge_SortDC(4+1,8)各自的执行顺序，也跟Merge_SortDC(1,8);是类似的，可以类推。
递归就是先递推调用到最后，然后再一层层返回来。