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

《林平君-算法设计与分析-5》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、南昌航空大学实验报告年月日课程名称：算法设计与分析实验名称：边排序边求倒置数个数班级：11201221姓名：林平君同组人：指导教师评定：签名：一．实验目的1.对问题进行分析，将其抽象，并设计出算法。2.将算法用程序代码实现。3.分析算法实现的效率。二．实验要求1.理解分治法的思想2.理解合并排序的思想3.利用合并排序的过程中实现倒置数的个数三．算法效率分析利用公式：T(n)=aT(n/b)+f(n)其中f(n)表示利用同治法后将原来的合并起来的时间：所以由Merge(inttempA[],inttempB[],intfinC[])函数可

2、知：f(n)Ɛθ(n^1)，故d=1,所以有a=b^d综上所述：T(n)Ɛθ(nlogn)四．源代码如下：publicclassConvertDivide{/***利用分治法求解倒置数*@paramargs*/publicstaticvoidmain(String[]args){//TODOAuto-generatedmethodstubint[]a=newint[]{1,8,6,7,2};System.out.println(divideNow(a));}staticpublicintdivideNow(inta[]){intnlen

3、gth=a.length;inttempA[];inttempB[];if(nlength==1)return0;else{//判断数组个数为奇数和偶数if(nlength%2==0){//数组个数为偶数的情况tempA=newint[nlength/2];tempB=newint[nlength/2];for(inti=0;i

4、A=newint[nlength/2];tempB=newint[nlength/2+1];for(inti=0;i<(int)nlength/2;i++){tempA[i]=a[i];}for(intj=0;j<(int)nlength/2+1;j++){tempB[j]=a[j+nlength/2];}}}intresultA=divideNow(tempA);intresultB=divideNow(tempB);intx=Merge(tempA,tempB,a);returnx+resultA+resultB;}staticpu

5、blicintMerge(inttempA[],inttempB[],intfinC[]){//边排序边计算倒置数量inti,j,k,flag=0;i=0;j=0;k=0;while(itempB[j]){flag=flag+1;finC[k++]=tempB[j++];}else{finC[k++]=tempA[i++];}}//当数组tempA已经插入完毕后，将tempB的后半段插入到数组finC中if(i==tempA.length){for(i

6、nte=j;e

7、用同治法可以降低算法的运行效率，提高程序的运行速度。