实验一算法分析础.docVIP

算法分析与设计实验报告 　　　　　　　　　　 教师 上课时间 实验一 算法分析基础 1. 实验目的 1.1．熟悉Eclipse中编辑、编译和运行JAVA程序的方法； 1.2．了解算法的定义与特点； 1.3．学会分析算法的时间复杂度和空间复杂度。 2. 实验环境 2.1 Eclipse 2.2 Window XP 3. 实验内容 3.1 排序问题：实现冒泡排序、插入排序算法，并分析它们的算法复杂度。 3.2 合并问题：合并两个已排序的表，并分析算法复杂度。（首先判断两个表是否已排序） 4. 教师批改意见 签字： ： 实验报告细表 1插入排序 1.1 算法设计思想 快速排序是通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。package 实验1; import java.util.Scanner; public class InsertionSort { public static void main(String anr[]){ int[] a=new int[7]; a[6] Scanner s = new Scanner(System.in); for(int i=1;i6;i++) { System.out.println(请输入第+i+个数字); a[i]=s.nextInt(); } for(int i=1;i6;i++) { if(a[i+1]a[i]){ a[0]=a[i+1]; for(int j=i+1;j0;j--) { a[j]=a[i]; i--; } } } System.out.println(插入排序后的顺序为：); for(int i=1;i6;i++) System.out.println(a[i]); } } 1.3 实验结论 第一组数据： 当输入数据为5,9,7,11,6时，结果如下： 第二组数据： 当输入数据为6,9,1,11,10时，结果如下： 第三组数据： 当输入数据为55,16,25,48,10时，结果如下： 1.4 心得体会 快速排序的运行时间与划分是否对称有关，算法的实现和理解与代码实现完全是两回事，想要完全掌握一种算法，需要动手实践，用代码实现，才能理解透彻，真正掌握。 2冒泡排序 2.1 算法设计思想 冒泡排序（Bubble Sort），是一种计算机科学领域的较简单的排序算法。 它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。 这个算法的名字由来是因为越大的元素会经由交换慢慢“浮”到数列的顶端，故名。 2.2 程序源码 插入排序代码： package 实验1; import java.util.Scanner; public class InsertionSort { public static void main(String anr[]){ int j=5; int[] a=new int[6]; a[0]=-999999999; Scanner s = new Scanner(System.in); for(int i=1;i6;i++) { System.out.println(请输入第+i+个数字); a[i]=s.nextInt(); } while(j0){ for(int i=5;i0;i--) { if(a[i]a[i-1]) { int temp; temp=a[i]; a[i]=a[i-1]; a[i-1]=temp; } } j--; } System.out.println(冒泡排序后的顺序为：); for(int i=1;i6;i++) System.out.println(a[i]); } } 第二组数据： 当输入数据为17,25,16,23,14时，结果如下： 第三组数据：