排序算法设计和比较

《排序算法设计和比较》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、实验五　排序算法设计和比较一、【实验内容与要求】问题描述：利用直接插入排序、冒泡排序、快速排序对数列进行排序。基本要求：（1）能随机生成30个值为0到100的数。（2）用于排序的输入数列可以是要求（1）中随机生成的，也可以是键盘输入。（3）输出结果为利用三种方法排序后的结果，并能显示三种算法时间、空间性能参数值。【测试数据】由随机自行生成若干个数，进行排序。二、程序设计的基本思想，原理和算法描述：（包括程序的结构，数据结构，输入/输出设计，符号名说明等）1）符号说明：m1，m2，m3代表三种排序法的循环次数a[],b[],c[]

2、分别用来存储三次排序的数据temp中间变量n参与排序的数字个数maopao（a，n）冒泡程序排序zhicha（b，n）直接插入排序quick(a,h,l)快速排序法h分块排序的上限l分块排序的下限2）程序说明（结构，输入输出）这个程序整个流程比较自然，一脉相传，即先输入要排序的个数，然后选择要输入的方式，将产生的数传到数组中，然后依次地用冒泡子程序，直接插入的程序，快速排序的方法，依次排序，并将排好的数输出，以及算法的时间复杂率。K=2K=1调用随机数函数，由随机产生n个数选择输入方式k？调用键盘输入函数，由键盘输入要比较的数（

3、n个数）START初始化函数，根据提示语句，输入要参加数字个数n同时将得到的数同步传到数组b[],c[];为下面各种排序做准备调用冒泡排序的子程序，传输参数，排序从大到小，并计算循环的次数，将结果输出调用直接插入子程序重复上面操作，输出结果。调用快速排序子程序，重复操作，输出结果。END3）程序流程图三、源程序及注释：#include"stdio.h"#include"time.h"intm1=0;全局变量定义冒泡法循环的次数intm2=0;全局变量定义直接插入法循环的次数intm3=0;全局变量定义快速法循环的次数intsui

4、ji(inta[],intn)；随机生成目的数函数{inti,j,temp;srand((unsigned)time(NULL));srand播下一个种子for(i=0;i

5、maopao(inta[],intn)冒泡法排序程序{inti,j,temp;for(i=0;ia[j-1]){temp=a[j];a[j]=a[j-1];a[j-1]=temp;}m1++;计算循环次数}printf("Bubbathesortednember:");for(i=0;i

6、tf("timeeffective:%d",m1);输出冒泡法的时间效率m1}zhicha(intb[],intn)直接插入排序子程序{inti,j,temp;printf("Direct:");for(i=1;i0&&temp>b[j-1];--j)具体排序过程{b[j]=b[j-1];m2++;}b[j]=temp;}for(i=0;i

7、rintf("timeeffective:%d",m2);输出时间效率}quick(intc[],intl,inth)快速排序法{inttemp;inti,j,k;i=l;j=h;if(ltemp){i++;m3++;}if(i

8、(c,i+1,h);递归调用排序}}main(){inti,j,k,n;inta[100],b[100],c[100];定义三个数组来存放三种方法的数字clrscr();清屏函数printf("inputnumber:");scanf("%d",&n);输入要参