实验算法分析基础

1、算法分析与设计实验报告学号姓名班级上课地点教师上课时间实验一算法分析基础1. 实验目的1.1 .熟悉Eclipse中编辑、编译和运行JAVA程序的方法；1.2. 了解算法的定义与特点；1.3. 学会分析算法的时间复杂度和空间复杂度。2. 实验环境2.1 Eclipse2.2 Win dow XP3. 实验内容3.1排序问题：实现冒泡排序、插入排序算法，并分析它们的算法复杂度。3.2合并问题：合并两个已排序的表，并分析算法复杂度。（首先判断两个表是否已排序）4.教师批改意见签字： 日期：成绩实验报告细表1插入排序1.1算法设计思想快速排序是通过一趟排序将要排序的数据分割成独立的两部分，其中一部分

2、的所有数据都比另外一部分的所有数据都要小， 然后再按此方法对这两部分数据 分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序 列。快速排序算法流程图为：1.2程序源码 插入排序代码：package 实验 1;import java.util.Sca nner;public class In serti on Sort public static void main(String anr)i nt a= new int 7;a6=99999999;Scanner s = _ new Scanner(System.in );for (int i=1;i<6;i+)Syst

3、em. out .println("请输入第"+i+ "个数字");ai=s. nextl nt();for ( int i=1;i<6;i+)if (ai+1<ai)a0=ai+1;for (int j=i+1;j>O;j-)aj=ai;System. out .println(”插入排序后的顺序为：");for ( int i=1;i<6;i+)System. out .println(ai);1.3实验结论第一组数据：当输入数据为5,9,7,11,6时，结果如下:诵*t入甲卜立于M淫入第4个IX活玩入帑5千差辛羞入

4、爭字吉紂牴宇却567吕11第二组数据：当输入数据为6,9,1,11,10时，结果如下:191011第三组数据：当输入数据为55,16,25,48,10时，结果如下:102542SS1.4心得体会快速排序的运行时间与划分是否对称有关， 算法的实现和理解与代码实现完 全是两回事，想要完全掌握一种算法，需要动手实践，用代码实现，才能理解透 彻，真正掌握。2冒泡排序2.1算法设计思想冒泡排序(Bubble Sort )，是一种计算机科学领域的较简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交 换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列

5、已经排序完成。这个算法的名字由来是因为越大的元素会经由交换慢慢浮”到数列的顶端，故名。冒泡排序算法流程图为：2.2程序源码 插入排序代码：package 实验 1;import java.util.Sca nner;public classIn serti on Sort public static void main(String anr)i nt j=5;i nt a= new int 6;a0=-999999999;Scanner s = _ new Scanner(System. in );for (int i=1;i<6;i+)System. out .println(&quo

6、t;请输入第"+i+ "个数字");ai=s. nextl nt();while (j>0)for ( int i=5;i>0;i-)if (ai<ai-1)int temp; temp=ai; ai=ai-1;ai-1=temp;j-；System. out .println( "冒泡排序后的顺序为：”);for ( int i=1;i<6;i+)System. out .println(ai);2.3实验结论第一组数据：当输入数据为12,26,8,23,19时，结果如下:12活&入籌2牛"宁2623活雜入第5

7、 丸宁1919第二组数据：当输入数据为17,25,16,23,14时，结果如下:靑建代穷1牛空芋17诗輦汽第2牛金丰25建皐人另3牛灯竽谒宅入雳却小蛊字2314诃色螂序启抑転子为1416172325第三组数据：当输入数据为150,156,28,199,233时，结果如下:1S0谴疇入肆2牛方孚156涛建入杲了牛盅宁2S诸建代主4牛空兰199诗星八第5 6克手233勇;冬爭子否笊枣牛台；281501561992332.4心得体会比起插入排序本题要来的更加简单，只要对比与输入数字相同次数的循环即可。1合并排序1.1算法设计思想合并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法(Di

8、videand Conquer )的一个非常典型的应用。合并排序法是将两个(或两个以上)有序表合并成一个新的有序表，即把待排序序列分为若干个子序列，每个子序列是有序的。然后再把有序子序列合并为整体有序序列。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为2-路归并。合并排序也叫归并排序。1.2程序源码合并排序代码：package 实验 1;import java.util.Sca nner;public class heb ing publicstaticvoid main(String arg)i nt a=newint

9、 5;i nt b=newint 5;i nt c=newint 10;Scanner s = new Scann er(System.in);System. out .println(“请按从小到大顺序输入第一串数字“)；for ( int i=0;i<5;i+)ai=s. nextl nt();System. out .println(”请按从小到大顺序输入第二串数字");for ( int j=0;j<5;j+)bj=s. nextl nt();int i = 0; int j = 0; int k=0;while (i<5&&j<5)i

10、 f (ai<bj)ck=ai;k+;i+；else if (bj<ai)ck=bj;k+;j+;elseck=ai;k+;i+;if (i=5)While (j<5)ck+=bj+;elseWhile (i<5)ck=ai;System. out .println(”合并排序后的顺序为：")；for (k=0;k<10;k+)System. out .print(ck+""); 1.3实验结论第一组数据：当输入数据为1,3,5,7,9与2,4,6,8,10时，结果如下:旦控倒台£3心已绣止* hebing Java 应用程

11、C:Pragrarri Files (xS再集认力氛六万手雜入講一芈;&手13 5 7 9-N琴乂小匪大咽丐翔人第二工忝壬2 A 6 8 IO123<567&910第二组数据:当输入数据，结果如下:控制台兔v已终止a hebing Java 也用程序C:Program F 背S典*監丸席骑t入第一军韭拿1 5 9 14 1S谒域張*盒玄寿=*A第二爭如芋1 6 7 1® 151 1 S 6 7 9 16 14 1B 19第三组数据：当输入数据，结果如下:国控制台£3卜歸止a Iw已纯止hebing Java应用程序C:Prograi诗S氏*盂皿（?#；