问答题
阅读下列说明和C代码，回答下面问题。
[说明]
采用归并排序对n个元素进行递增排序时，首先将n个元素的数组分成各含n/2个元素的两个子数组，然后用归并排序对两个子数组进行递归排序，最后合并两个已经排序的子数组得到排序结果。
下面的C代码是对上述归并算法的实现，其中的常量和变量说明如下。
●art：待排序数组。
●p，q，r：一个子数组的位置从p到q，另一个子数组的位置从q+1到r。
●begin，end：待排序数组的起止位置。
●left，right：临时存放待合并的两个子数组。
●n1，n2：两个子数组的长度。
●i，j，k：循环变量。
●mid：临时变量。
[C代码]
#inciude＜stdio.h＞
#inciude＜stdlib.h＞
Define MAX 65536
void merge(int art([],int p,int q,int r)
{
int*left,*right;
int n1,n2,I,j,k;
n1=q-p+1;
n2=r-q;
If(left=(int*)malloc((n1+1)*sizeof(int)))=NULL)
{
Perror("malloc error");
exit(1);
}
If((right=(int*)malloc((n2+1)*sizeof(int)))=NULL)
{
Perror("malloc error");
exit(1);
}
for(i=0;i＜n1;i++)
{
left[i]=art[p+i];
}
left[i]=MAX;
for(i=0;i＜n2;i++)
{
right[i]=arr[q+i+1]
}
right[i]=MAX;
i=0;j=0;
For(k=p;(1);k++)
{
If(left[i]＞right[j]
{
______
j++;
}
else
{
arr[k1]=left[i];
i++;
}
}
}
Void merge Sort(int art(),int begin,int end)
{
int mid;
if(______)
{
mid=(begin+end)/2;
merge Sort(art,begin,mid);
______;
Merge(arr,begin,mid,end);
}
}
问答题
根据以上说明和C代码，填充各个空。
【正确答案】
【答案解析】k＜=r
arr[k]=right[j]
begin＜end
mergeSort(arr,mid+1,end)
[解析] 首先，函数voidmerge(int arr[],int p,int q,int r)的意思是：对子数组arr[p..q]和子数组arr[q+L..r]进行合并，因此第一个空为k＜=q;由于是采用归并排序对n个元素进行递增排序，所以第二个空是将left[i]和right[j]的较小者存放到arr[k]中去，即arr[k]=right[j]：当数组长度为1时，停止递归，因为此时该数组有序，则第三个空为begin＜end，即数组至少有两个元素才进行递归，合并了begin到mid之间的元素，继续合并mid+1到end之间的元素，则第四个空为mergeSort(arr,mid+1,end)。
问答题
根据题干说明和以上C代码，算法采用了______算法设计策略，分析时间复杂度时，列出其递归式为______，
接触渐进时间复杂度______(用O符号表示)，空间复杂度为______(用O符号表示)。
【正确答案】
【答案解析】分治
T(n)=2T(n/2)+O(n)
O(nlogn)
O(n)
[解析] 归并算法实际上就是将数组一直往下分割，直到分割到由一个元素组成的n个子数组，再往上两两归并。
将数组进行分割需要logn步，因为每次都是将数组分割成两半(2
x
=n，x=logn)。
合并n个元素，需要进行n步，也就是O(n)，则总的时间复杂度为O(nlogn)。
在合并过程中，使用了n个中间变量存储，left=(int*)malloc((n1+1)*sizeof(int))，所以空间复杂度为O(n)。
推导递归式：假设n个元素进行归并排序需要T(n)，可以将其分割成两个分别包括n/2个元素的数组分别进行归并，也就是2T(n/2)，在将这两个数组合并，需要O(n)的时间复杂度，则推导公式为T(n)=2T(n/2)+O(n)。
问答题
两个长度分别为n1和n2的已经排好序的子数组进行归并，根据上述C代码，则元素之间的比较次数为______。
【正确答案】
【答案解析】n1+n2
[解析] 假定有这样两个有序数组L1:{a1,a2,…,an}和L2:{b1,b2,…,bn}，简单归并，就是逐个比对，没有跳跃优化(skip)的。
在最好的情况下，归并后的结果为{a1,a2,…,an,b1,b2,…,bn}或者{b1,b2,…,bn,a1,a2,…,an}，比较的次数显然为n次(n/2+n/2)，出现前者或者后者的概率均为1/2
在最坏的情况下，归并后的结果为{a1,b1,a2,b2,…,an,bn}或者{b1,a1,b2,a2,…,bn,an}，不妨考察前者，L1或L2中任意一个(除bn以外)要想确定自己的位置，必须进行一次比较，因此总的比较次数为2n-1。
再考察平均情况：假定归并后的结果为{{b1,…,br}{a1,…,an-1}||anbr+1,…,bn-1bn}，这表示任意的b1..br共计r个来自L2的b序列，a1..an-1共计n-1个来自L1的a序列的数字组合成的一个串。
该串共计有C(r+n-1，r)种可能性，这r+n-1个数每个数要想确定自己的位置都需要进行一次比较，因此比较次数是n+r次，而an和bn-r相比，确定自己更小，还需要1次，因此总计的比较次数是n+r，根据上述解释，若题目中有长度为n1和n2的两个有序数组进行归并，则总计的比较次数为n1+n2。