林平君-算法设计与分析-5.docx

南昌航空大学实验报告 年 月 日课程名称： 算法设计与分析 实验名称： 边排序边求倒置数个数 班级： 11201221 姓名： 林平君 同组人： 指导教师评定： 签名： 一 实验目的1. 对问题进行分析，将其抽象，并设计出算法。2. 将算法用程序代码实现。3. 分析算法实现的效率。二 实验要求1. 理解分治法的思想2. 理解合并排序的思想3. 利用合并排序的过程中实现倒置数的个数三 算法效率分析利用公式：T(n)=aT(n/b)+f(n)其中f(n)表示利用同治法后将原来的合并起来的时间：所以由Merge(int tempA,int tempB,int finC)函数可知：f(n)(n1)，故d=1,所以有a=bd综上所述：T(n)(nlogn)四 源代码如下：public class ConvertDivide /* * 利用分治法求解倒置数 * param args */public static void main(String args) / TODO Auto-generated method stubint a=new int1,8,6,7,2;System.out.println(divideNow(a); static public int divideNow(int a)int nlength=a.length;int tempA;int tempB;if(nlength=1)return 0;else /判断数组个数为奇数和偶数if(nlength%2=0)/数组个数为偶数的情况tempA=new intnlength/2;tempB=new intnlength/2;for(int i=0;inlength/2;i+)tempAi=ai;for(int j=0;jnlength/2;j+)tempBj=aj+nlength/2;else /数组个数为奇数的情况tempA=new intnlength/2;tempB=new intnlength/2+1;for(int i=0;i(int)nlength/2;i+)tempAi=ai;for(int j=0;j(int)nlength/2+1;j+)tempBj=aj+nlength/2;int resultA=divideNow(tempA);int resultB=divideNow(tempB);int x=Merge(tempA, tempB, a);return x+resultA+resultB; static public int Merge(int tempA,int tempB,int finC)/边排序边计算倒置数量int i,j,k,flag=0;i=0;j=0;k=0;while(itempA.length&jtempBj)flag=flag+1;finCk+=tempBj+;elsefinCk+=tempAi+;/当数组tempA已经插入完毕后，将tempB的后半段插入到数组finC中if(i=tempA.length)for(int e=j;etempB.length;e+)finCk+=tempBe;else /当数组tempB已经插入完毕后，将tempA的后半段插入到数组finC中for(int e=i;etempA.length;e+)finCk+=tempAe;return flag;五 实验结果1.设置数组为：int a=new int1,8,6,7,2; 结果是：52. 设置数组为：int a=ne