资源描述：
《内部排序算法比较.doc》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。
1、内部排序算法比较班级：姓名：学号：完成日期：题目：试通过随机数据比较各算法的关键字比较次数和关键字移动次数，以取得直观感受。一．需求分析1.对常用的6种内部排序算法进行比较：冒泡排序，直接插入排序，简单选择排序，快速排序，希尔排序，堆排序。2.待排序表的表长不小于100；其中的数据要用伪随机数产生程序产生；至少要用5组不同的输入数据作比较；比较的指标为有关键字参加的比较次数和关键字的移动次数（关键字交换计为3次移动）3.最后要对结果作出简单分析，包括对各组数据得到结果波动大小的解释。二．概要设计1.主界面设计对六种内部排序算法进行比较，可通过随机数
2、程序产生几组数，要求用户手动输入产生随机数的个数。运行界面如图所示：选择1运行程序，选择2退出程序2．存储结构设计本程序采用顺序表结构，具体结构定义如下：typedefstruct{intkey;}ElemType;typedefstruct{ElemType*elem;intlength;}SqList;最新可编辑word文档3.系统功能设计1）分配内存空间。创建顺序表2）利用伪随机数产生程序产生随机数，作为程序运行的数据3）实现每种排序算法的功能函数三．模块设计随机数产生模块1.模块设计主程序模块排序算法模块2.系统子程序及功能设计本系统共设置
3、13个函数，其中包括主函数。各函数名及功能说明如下。1）voidaddlist(SqList&L)//建立个空顺序表2）voidrandom(SqList&L)//随机数产生函数3）voidmemory(SqList&M,SqList&L)//记录L，以保证每个排序函数使用一组随机数4）voidBubbleSort(SqList&L)//冒泡排序5）voidInsertSort(SqList&L)//直接插入排序6）voidSelectSort(SqList&L)//选择排序7）intPartition(SqList&L,intlow,inthig
4、h)//返回快速排序枢轴的位置8）voidQSort(SqList&L,intlow,inthigh)//对子序列作快速排序9）voidQuickSort(SqList&L)//对数序表作快速排序10）voidShellSort(SqList&L)//希尔排序11）voidHeapAdjust(SqList&L,ints,intm)//堆排序算法子程序12）voidHeapSort(SqList&L)//对顺序表进行堆排序13）voidmain()//主函数，调用各模块函数3.函数主要调用关系最新可编辑word文档913）main（）5124321
5、1068117四．详细设计1.数据类型定义typedefstruct{intkey;}ElemType;typedefstruct{ElemType*elem;intlength;}SqList;2.全局变量定义intbj1=0,yd1=0,bj2=0,yd2=0,bj3=0,yd3=0,bj4=0,yd4=0,bj5=0,yd5=0,bj6=0,yd6=0;//记录每种算法的比较，移动次数intn；//随机数的个数2.系统主要子程序详细设计（1）主函数设计模块主要是输入数据，以及程序界面的设计，调用系统的各个子程序，并输出结果。（详见源程序）（2
6、）随机数产生模块利用伪随机数产生程序产生数据，并存储到顺序表中。voidrandom(SqList&L){L.length=0;staticboolfirst=true;if(first){srand(time(0));first=false;}//使每次产生的随机数不同for(inti=1;i30000)gotoa;++L.length;}（3）排序算法模块实现冒泡排序，直接插入排序，简单选择排序，快速排序，希尔排序以及堆排序
7、的算法。（祥见源程序）五．测试分析运行程序后，得到如图所示：输入：1输入：100选择1重复上述步骤，输入150，200，250，300得到另外四个结果：最新可编辑word文档退出程序，请选择：2最新可编辑word文档结果分析：冒泡排序，直接插入排序以及简单选择排序比较次数较多，快速排序，希尔排序及堆排序比较次数较少；并可得冒泡排序和直接插入排序相对较稳定，其他四种内部排序为不稳定排序。六．源程序清单#include"iostream"#include"stdio.h"#include"stdlib.h"#include"string.h"#incl
8、ude"time.h"usingnamespacestd;#defineLIST_INIT_SIZE50000intbj1
