java数据结构大作业.pdf

上海电力学院上海电力学院数据结构（数据结构（JAJAV VA A）课程设计）课程设计题目:学生姓名：学号：院系：专业年级：21.*各种排序算法时间性能比较20122014年1月日15目录目录一、设计题目一、设计题目.2.2二、需求分析二、需求分析.2.2三、概要设计三、概要设计.2.2四、详细设计四、详细设计.4.4五、调试分析五、调试分析.11.11六、创新点六、创新点.13.13七、附录：程序设计源代码七、附录：程序设计源代码.13.131一、设计题目一、设计题目1)1)问题描述问题描述对各种排序方法（直接插入排序、希尔排序、起泡排序、快速排序、直接选择排序、堆排序和归并排序）的时间性能进行比较。2)2)基本要求基本要求(1)设计并实现上述各种排序算法；(2)产生正序和逆序的初始排列分别调用上述排序算法，并比较时间性能；(3)产生随机的初始排列分别调用上述排序算法，并比较时间性能。二、需求分析二、需求分析1 1）运行环境（软、硬件环境）运行环境（软、硬件环境）开发工具：JDK1.6 eclipse10.0运行环境：Windows XP 及其以上系统2 2）输入的形式和输入值的范围）输入的形式和输入值的范围用户先自定义数组长度，再根据提示输入数组。3 3）输出的形式描述）输出的形式描述输出 4 个排序功能分别对于用户输入的数组进行排序后，所移动的次数，比较的次数，以及相应的运行时间。4 4）功能描述）功能描述能用多种排序算法对相应数组进行正序，逆序排序。能对随机生成的数组进行排序并输出相应时间。5 5）测试数据）测试数据用户输入的数据。三、概要设计三、概要设计1 1）抽象数据类型定义描述）抽象数据类型定义描述n数组长度循环变量table数组temp temp1临时变量22 2）功能模块设计（如主程序模块设计）功能模块设计（如主程序模块设计）Zhujiemian主程序Shunxu顺序，调用4个排序，输出结果Nixu逆序，调用4个排序，输出结果Rradom随机生成数组，调用排序方法，输出结果Paixu包含 4 种排序算法Insertsort直接插入排序Shellsort希尔排序bubblesort冒泡排序Selectsort直接选择排序3 3）模块层次调用关系图）模块层次调用关系图主界面Zhujiemian顺序shunxu逆序nixu随机ramdomramdom排序paixupaixu直接插入排序insertsort希尔排序shellsort冒泡排序bubblesort直接选择排序selectsort3四、详细设计四、详细设计主页面主页面importimport java.util.*;/引入包，使实现reader功能publicpublic classclass zhujiemian/主界面 publicpublic staticstatic intint table;/定义数组tableSystem.out.println(1.对数组进行顺序排序);publicpublic staticstatic voidvoid main(String args)intint n=0;/定义循环变量whilewhile(n!=4)/进行循环 System.out.println(2.对数组进行逆序排序);System.out.println(3.产生10个随机数组比较各时间性能);System.out.println(4.退出);Scanner reader=newnew Scanner(System.in);/读入数据 n=reader.nextInt();switchswitch(n)casecase 1:shunxu();breakbreak;casecase 2:nixu();breakbreak;casecase 3:Rradom();breakbreak;casecase 4:breakbreak;defaultdefault:breakbreak;publicpublic staticstatic voidvoid shunxu()/顺序4 Scanner reader=newnew Scanner(System.in);System.out.println(请输入数组的长度：);intint i=reader.nextInt();/读入数据itable=newnew intinti;/声明并创建数组initA(table,i);paixu px=newnew paixu();/运行排序方法px.insertSort(table);px.shellSort(table);px.bubbleSort(table);px.selectSort(table);publicpublic staticstatic voidvoid nixu()/逆序intint t;Scanner reader=newnew Scanner(System.in);publicpublic staticstatic voidvoid Rradom()/随机排序String s1=nullnull,s2=nullnull;/定义空串，用于之后排序算法的System.out.println(请输入数组长度：);intint i=reader.nextInt();table=newnew intinti;initA(table,i);paixu px=newnew paixu();px.insertSort(table);px.shellSort(table);px.bubbleSort(table);px.selectSort(table);比较intint min,num1=0,max,num2=0,j;table=newnew intint10;initB(table,10);paixu px=newnew paixu();px.insertSort(table);px.shellSort(table);px.bubbleSort(table);5px.selectSort(table);min=px.n0;max=px.n0;forfor(j=1;j3;j+)ifif(px.njmax)num2=j;max=px.nj;num1=j;min=px.nj;switchswitch(num1)casecase 0:s1=直接插入排序;breakbreak;casecase 1:s1=希尔排序;breakbreak;casecase 2:s1=冒泡排序;breakbreak;casecase 3:s1=直接选择排序;breakbreak;defaultdefault:breakbreak;switchswitch(num2)casecase 0:s2=直接插入排序;breakbreak;casecase 1:s2=希尔排序;breakbreak;casecase 2:s2=冒泡排序;breakbreak;casecase 3:s2=直接选择排序;breakbreak;defaultdefault:breakbreak;System.out.println(最佳排序：+s1);System.out.println(最差排序：+s2);6publicpublic staticstatic voidvoid initA(intinttable,intint n)System.out.println(请输入数组:);forfor(intint i=0;in;i+)Scanner reader=newnew Scanner(System.in);tablei=reader.nextInt();publicpublic staticstatic voidvoid initB(intint table,intint n)/产生随机数组forfor(intint i=0;in;i+)tablei=(intint)(Math.random()*50);/产生050之间的随机数排序代码：排序代码：publicpublic classclass paixu publicpublic staticstatic intint n=newnew intint4;publicpublic staticstatic intint m=newnew intint4;/n是比较次数，m是交换次数；publicpublicvoidvoid insertsort(intinttable)/直接插入排序longlong t0,t1,t2;t0=System.nanoTime();/定义时间 forfor(intint i=1;i=0&temptablej;j-)/将前面较大的元素向后移动 tablej+1=tablej;tablej+1=temp;/temp值达到插入位置 intint temp2=newnew intinttable.length;forfor(intint i=1;i=0&temp10;delta/=2)/若干趟扫描，控制增量，增量减半 n1+;forfor(intint i=delta;i=0&temptablej;j-=delta)8/每组元素相距delta远，寻找插入位置 tablej+delta=tablej;n1+;tablej+delta=temp;m1+;System.out.println(希尔排序);System.out.println(比较次数是：+n1);System.out.println(交换次数是：+m1);t1=System.nanoTime();t2=t1-t0;System.out.println(该排序所运行时间为+t2+纳秒);publicpublic voidvoid bubbleSort(intinttable)/冒泡排序 /是否交换的标记longlong t0,t1,t2;t0=System.nanoTime();booleanboolean exchange=truetrue;forfor(intint i=1;itable.length&exchange;i+)/有交换时再进行下一趟，最多n-1趟 exchange=falsefalse;/假定元素未进行交换n2+;forfor(intint j=0;jtablej+1)/反序时，交换 intint temp1=tablej;tablej=tablej+1;tablej+1=temp1;9 exchange=truetrue;/有交换 m2+=2;n2+;System.out.println(冒泡排序);System.out.println(比较次数是：+n2);System.out.println(交换次数是：+m2);t1=System.nanoTime();t2=t1-t0;System.out.println(该排序所运行时间为+t2+纳秒);publicpublic voidvoid selectSort(intinttable)/直接选择排序longlong t0,t1,t2;t0=System.nanoTime();forfor(intint i=0;itable.length-1;i+)/n-1趟排序 /每趟在从i开始的子序列中寻找最小元素intint min=i;/设第i个数据元素最小n3+;forfor(intint j=i+1;jtable.length;j+)/在子序列中查找最小值 ifif(tablejtablemin)min=j;/记住元素最小值下标 ifif(min!=i)/将本趟最小元素交换到前边 intint temp1=tablei;tablei=tablemin;10 tablemin=temp1;m3+=3;System.out.println(直接选择排序);System.out.println(比较次数是：+n3);System.out.println(交换次数是：+m3);t1=System.nanoTime();t2=t1-t0;System.out.println(该排序所运行时间为+t2+纳秒);五、调试分析五、调试分析1)1)、用户操作界面、用户操作界面2 2）、对数组进行顺序排序）、对数组进行顺序排序排序结果114 4）、逆序排序、逆序排序逆序排序和和顺序排序操作相似。5 5）、对随机数组进行排序：、对随机数组进行排序：输入 3 进入随机数组的排序，排序结果：126 6）、调试时面临的错误与解决方法、调试时面临的错误与解决方法在调试中，开始比较次数和交换次数显示不正常，后来发现是自己在算法中出错。在老师的指导下认识了 debug 的使用方法，这点收货非常大。六、创新点六、创新点在第一节课老师的指点下，自己去了解了关于获取程序当前时间的相关知识，通过排序方法前后时间相减，得到该排序所需时间，并且精确到了纳秒，让排序的时间性能看起来更加直观。七、七、附录：程序设计源代码附录：程序设计源代码importimport java.util.*;publicpublic classclass zhujiemian publicpublic staticstatic intint table;publicpublic staticstatic voidvoid main(String args)intint n=0;whilewhile(n!=4)System.out.println(1.对数组进行顺序排序);System.out.println(2.对数组进行逆序排序);System.out.println(3.产生10个随机数组比较各时间性能);System.out.println(4.退出);Scanner reader=newnew Scanner(System.in);n=reader.nextInt();switch(n)casecase 1:shunxu();breakbreak;casecase 2:nixu();breakbreak;casecase 3:Rradom();breakbreak;casecase 4:breakbreak;defaultdefault:breakbreak;13 publicpublic staticstatic voidvoid shunxu()/顺序 Scanner reader=newnew Scanner(System.in);System.out.println(请输入数组的长度：);intint i=reader.nextInt();table=newnew intinti;initA(table,i);paixu px=newnew paixu();px.insertSort(table);px.shellSort(table);px.bubbleSort(table);px.selectSort(table);publicpublic staticstatic voidvoid nixu()/逆序intint t;Scanner reader=newnew Scanner(System.in);publicpublic staticstatic voidvoid Rradom()/随机排序String s1=nullnull,s2=nullnull;14System.out.println(请输入数组长度：);intint i=reader.nextInt();table=newnew intinti;initA(table,i);paixu px=newnew paixu();px.insertSort(table);px.shellSort(table);px.bubbleSort(table);px.selectSort(table);intint min,num1=0,max,num2=0,j;table=newnew intint10;initB(table,10);paixu px=newnew paixu();px.insertSort(table);px.shellSort(table);px.bubbleSort(table);px.selectSort(table);min=px.n0;max=px.n0;forfor(j=1;j4;j+)ifif(px.njmax)num2=j;max=px.nj;num1=j;min=px.nj;switchswitch(num1)casecase 0:s1=直接插入排序;breakbreak;casecase 1:s1=希尔排序;breakbreak;casecase 2:s1=冒泡排序;breakbreak;casecase 3:s1=选择排序;breakbreak;defaultdefault:breakbreak;switchswitch(num2)casecase 0:s2=直接插入排序;breakbreak;casecase 1:s2=希尔排序;breakbreak;15casecase 2:s2=冒泡排序;breakbreak;casecase 3:s2=选择排序;breakbreak;defaultdefault:breakbreak;System.out.println(最佳排序：+s1);System.out.println(最差排序：+s2);publicpublic staticstatic voidvoid initA(intinttable,intint n)System.out.println(请输入数组:);forfor(intint i=0;in;i+)Scanner reader=newnew Scanner(System.in);tablei=reader.nextInt();publicpublic staticstatic voidvoid initB(intint table,intint n)forfor(intint i=0;in;i+)tablei=(intint)(Math.random()*10);publicpublic classclass paixu publicpublic staticstatic intint n=newnew intint4;publicpublic staticstatic intint m=newnew intint4;publicpublicvoidvoid insertSort(intinttable)longlong t0,t1,t2;t0=System.nanoTime();forfor(intint i=1;i=0&temptablej;j-)16 tablej+1=tablej;tablej+1=temp;intint temp2=newnew intinttable.length;forfor(intint i=1;i=0&temp10;delta/=2)n1+;forfor(intint i=delta;i=0&temptablej;j-=delta)tablej+delta=tablej;n1+;tablej+delta=temp;m1+;System.out.println(希尔排序);System.out.println(比较次数是：+n1);System.out.println(交换次数是：+m1);t1=System.nanoTime();t2=t1-t0;System.out.println(该排序所运行时间为+t2+纳秒);publicpublic voidvoid bubbleSort(intinttable)longlong t0,t1,t2;t0=System.nanoTime();booleanboolean exchange=truetrue;forfor(intint i=1;itable.length&exchange;i+)exchange=falsefalse;n2+;forfor(intint j=0;jtablej+1)18 intint temp1=tablej;tablej=tablej+1;tablej+1=temp1;exchange=truetrue;m2+=2;n2+;System.out.println(冒泡排序);System.out.println(比较次数是：+n2);System.out.println(交换次数是：+m2);t1=System.nanoTime();t2=t1-t0;System.out.println(该排序所运行时间为+t2+纳秒);publicpublic voidvoid selectSort(intinttable)longlong t0,t1,t2;t0=System.nanoTime();forfor(intint i=0;itable.length-1;i+)intint min=i;n3+;forfor(intint j=i+1;jtable.length;j+)ifif(tablejtablemin)min=j;ifif(min!=i)intint temp1=tablei;19 tablei=tablemin;tablemin=temp1;m3+=3;System.out.println(直接选择排序);System.out.println(比较次数是：+n3);System.out.println(交换次数是：+m3);t1=System.nanoTime();t2=t1-t0;System.out.println(该排序所运行时间为+t2+纳秒);20