1. 实验目的1掌握递归技术的基本思想并能编写程序进行算法实现。2能够实现归并排序算法。2. 实验任务及步骤任务 归并排序递归算法的设计与实现第 1 步每次将数组分解为左右两部分。第 2 步递归地求解子问题注意递归结束的条件。第 3 步将两个有序的子数组合并。修改下述代码中MergeSort()函数标红的三行代码处使程序输出正确结果并在所有标//注释的 10 处加代码注释。#includeiostreamusingnamespacestd;constintN10;voidMerge(inta[],intb[],intl,intm,intr)//注释1合并两个有序区间a[l,m]和a[m1,r]结果存入b数组{intil,jm1,kl,q;while((im)(jr))//注释2i指向左段起点j指向右段起点k是b数组当前存放位置两区间还有未处理元素时循环{if(a[i]a[j])//注释3取较小的数放入b数组确保升序b[k]a[i];elseb[k]a[j];}if(im)//注释4如果左区间已经取完直接复制右区间剩余元素{for(qj;qr;q)b[k]a[q];}else{for(qi;qm;q)b[k]a[q];}}voidMergeSort(inta[],intb[],intleft,intright){//注意传数组给一个函数数组类型自动转换为指针类型传的实际是地址。if(leftright)//注释5递归终止条件区间仅有1个元素时停止递归{inti(leftright)/2;//注释6计算区间中点将数组拆成左右两个区间MergeSort(a,b,left,i);////注释7递归排序左半区间[left,mid]MergeSort(a,b,i1,right);//注释8递归排序右半区间[mid1,right]Merge(a,b,left,i,right);//注释9合并排好序的两区间for(ileft;iright;i)a[i]b[i];//注释10把临时数组b中合并好的数据复制回原数组a}}intmain(){inti;inta[N],b[N];for(i0;iN;i){a[i]N-i;couta[i] ;}coutendl;MergeSort(a,b,0,N-1);for(i0;iN;i)couta[i] ;coutendl;return0;}代码说明标红的三行代码即注释6、注释7、注释8三处原代码中这三行被错误地写成了int i0;、MergeSort(a,b,0,0);、MergeSort(a,b,0,0);导致递归无法正确拆分区间。修正后int i(leftright)/2;计算区间中点MergeSort(a,b,left,i);递归排序左半区间MergeSort(a,b,i1,right);递归排序右半区间。程序运行后原数组10 9 8 7 6 5 4 3 2 1将被排序为1 2 3 4 5 6 7 8 9 10。3. 实验总结递归时间复杂度的分析常用方法递归时间复杂度的分析常用方法有代入法、递归树法、主定理。代入法先猜测递归式的时间复杂度上界/下界再用数学归纳法验证猜想是否成立。递归树法把递归展开画成树每一层代表一次递归调用累加每一层的代价求和得到总时间复杂度适合直观分析分治类递归。主定理针对形如T(n)aT(n/b)f(n)的分治递归式直接套用公式快速得出复杂度归并排序就是典型例子。归并排序复杂度分析归并排序满足主定理形式T(n)2T(n/2)O(n)其中a2、b2、f(n)O(n)因此时间复杂度为O(n log n)空间复杂度为O(n)需要临时数组b。