实验五排序算法设计和比较

实验五 排序算法设计和比较

一、【实验内容与要求】

问题描述：利用直接插入排序、冒泡排序、快速排序对数列进行排序。

基本要求：

（1） 能随机生成30个值为0到100的数。

（2） 用于排序的输入数列可以是要求（1）中随机生成的，也可以是键盘

输入。

（3） 输出结果为利用三种方法排序后的结果，并能显示三种算法时间、空

间性能参数值。

【测试数据】

由随机自行生成若干个数，进行排序。

二、程序设计的基本思想，原理和算法描述：

（包括程序的结构，数据结构，输入/输出设计，符号名说明等） 1） 符号说明：

m1，m2，m3 代表三种排序法的循环次数 a[],b[],c[] 分别用来存储三次排序的数据 temp 中间变量

n 参与排序的数字个数 maopao（a，n） 冒泡程序排序 zhicha（b，n） 直接插入排序 quick(a,h,l) 快速排序法 h 分块排序的上限 l 分块排序的下限

2） 程序说明（结构，输入输出）

这个程序整个流程比较自然，一脉相传，即先输入要排序的个数，然后选择要输入的方式，将产生的数传到数组中，然后依次地用冒泡子程序，直接插入的程序，快速排序的方法，依次排序，并将排好的数输出，以及算法的时间复杂率。

3）程序流程图

同时将得到的数同步传到数组b[],c[];为下面各种排序做准备 选择输入方式k？ K=1 调用随机数函数，由随机产生n个数 初始化函数，根据提示语句，输入要参加数字个数n START K=2 调用键盘输入函数，由键盘输入要比较的数（n个数）

调用直接插入子程序重复上面操作，输出结果。 调用冒泡排序的子程序，传输参数，排序从大到小，并计算循环的次数，将结果输出 调用快速排序子程序，重复操作，输出结果。 END 三、源程序及注释：

#include\#include\

int m1=0;全局变量定义冒泡法循环的次数

int m2=0; 全局变量定义直接插入法循环的次数 int m3=0; 全局变量定义快速法循环的次数 int suiji(int a[],int n) ；随机生成目的数函数 { int i,j,temp;

srand((unsigned)time(NULL)); srand播下一个种子 for(i=0;i

jianpan(int a[],int n) 键盘输入目的数函数 { int i,j,k,l;

for(i=0;i

maopao(int a[],int n) 冒泡法排序程序 { int i,j,temp;

for(i=0;i

for(j=1;j<(n-i);j++) ；具体的排序过程 {if(a[j]>a[j-1]) { temp=a[j]; a[j]=a[j-1]; a[j-1]=temp;

} m1++; 计算循环次数

} printf(\ for(i=0;i

zhicha(int b[],int n) 直接插入排序子程序 {

int i,j,temp;

printf(\ for(i=1;i0&&temp>b[j-1];--j) 具体排序过程 {b[j]=b[j-1];m2++;} b[j]=temp; } for(i=0;i

quick(int c[],int l,int h) 快速排序法 { int temp; int i,j,k; i=l;j=h; if(ltemp) { i++; m3++;} if(i

{ int i,j,k,n;

int a[100],b[100],c[100]; 定义三个数组来存放三种方法的数字 clrscr(); 清屏函数

printf(\

scanf(\ 输入要参与排序的数目

printf(\ scanf(\选择输入的方式 if(k==1) k=1 则调用随机函数调用 {suiji(a,n);}

if(k==2) k=2 则调用键盘输入函数 { jianpan(a,n); } for(i=0;i

maopao(a,n); 调用冒泡法程序 zhicha(b,n); 调用直接插入排序 printf(\

quick(c,0,n-1); 调用快速排序法 for(i=0;i

{ printf(\ %d\

if((i+1)%5==0) printf(\ }

printf(\ getchar(); getchar(); }??

四、运行输出结果：

五、调试和运行程序过程中产生的问题及采取的措施：

在写程序的过程思路比较清晰，遇到的困难主要是编程软件的不兼容，或是某些c语言规则在一些软件上为非法的，早先我用的一直用地是devC++，但是在用随机生成数子函数，一直提示有错误，改正不了，最后只好用最原始的turbo C问题解决了，发现最好用的还是tc啊，以后只用突出（我电脑一直装不了vc++，不知道怎么回事），在具体编程中需要考虑的是函数形参和实参的格式，一定要一致。

六、对算法的程序的讨论、分析，改进设想，其它经验教训：

这次程序中主要用三种排序方法：a。冒泡排序b直接插入排序c。快速排序。其中 冒泡排序的时间复杂度：O(n2) 空间复杂度：O(1) 直接插入排序时间复杂度：O(n2) 空间复杂度：O(1) 序法 冒泡排序 快速排序 选择排序 二叉树排序 插入排序

最差时间分析 O(n2) O(n2) O(n2) O(n2) O(n2) 平均时间复杂度 O(n2) O(n*log2n) O(n2) O(n*log2n) O(n2) 稳定度 稳定 不稳定 稳定 不一顶 稳定 空间复杂度 O(1) O(log2n)~O(n) O(1) O(n) O(1)

六、对算法的程序的讨论、分析，改进设想，其它经验教训：

这次程序中主要用三种排序方法：a。冒泡排序b直接插入排序c。快速排序。其中 冒泡排序的时间复杂度：O(n2) 空间复杂度：O(1) 直接插入排序时间复杂度：O(n2) 空间复杂度：O(1) 序法 冒泡排序 快速排序 选择排序 二叉树排序 插入排序

最差时间分析 O(n2) O(n2) O(n2) O(n2) O(n2) 平均时间复杂度 O(n2) O(n*log2n) O(n2) O(n*log2n) O(n2) 稳定度 稳定 不稳定 稳定 不一顶 稳定 空间复杂度 O(1) O(log2n)~O(n) O(1) O(n) O(1)

本文来源：https://www.bwwdw.com/article/up58.html