《内部排序算法实现与性能分析课程设计综述》由会员分享，可在线阅读，更多相关《内部排序算法实现与性能分析课程设计综述（14页珍藏版）》请在金锄头文库上搜索。
1、 目 录1、问题描述：31.1题目内容:31.2基本要求:31.3测试数据:32、需求分析：32.1程序的基本功能:32.2输入值、输出值以及输入输出形式:32.3各个模块的功能要求：33、概要设计：43.1所需的ADT，每个程序中使用的存储结构设计说明43.2主程序流程以及模块调用关系43.3每个模块的算法设计说明（流程图）53.3.1气泡排序：53.3.2直插排序63.3.3选择排序73.3.4希尔排序83.3.5快速排序94、详细设计：104.1函数调用关系图105、各个算法实现的源程序：105.1、冒泡排序及其主要算法105.2、直接插入排序及其主要算法115.3、选择排序及其主要算法
2、115.4、希尔排序及其主要算法126、调试分析：137、使用说明：148、测试结果：159、主要参考文献151、问题描述：1.1题目内容: 内部排序算法实现与性能分析1.2基本要求:（1）数据结构定义（2）利用随机函数产生30000个随机整数，利用插入排序、起泡排序、选择排序、快速排序、希尔等排序方法进行排序，并统计每一种排序上机所花费的时间,对各种排序算法做分析比较.1.3测试数据: 由函数随机产生的数据，由于是随机产生的，所以在此不一一写出。2、需求分析：2.1程序的基本功能:输入30000个随机整数，对这些数进行多种方法进行排序，并对这些排序做比较，在屏幕上输出每种排序方法所比较的次数
3、，交换的次数，和时间复杂度。2.2输入值、输出值以及输入输出形式:由于程序中所需的数据都是有函数随机生成的整形数，不需要用户自己输入，用户只需要对演示程序中的一些提示做一些必要的选择以便于程序的执行。程序输出的是对六种排序做的一些比较，即输出六种排序各排序过程中所比较的数据的个数，交换的数据的次数，和排序完成所用的时间。六种排序依次在计算机终端上显示，便于用户观察。2.3各个模块的功能要求：一、随机函数：产生随机数 二、选择排序函数：对随机数进行选择排序 三、起泡排序函数：对随机数进行气泡排序四、直接插入函数：对随机数进行直接插入排序 五、希尔排序函数：对随机数进行希尔排序 六、快速排序函数：
4、对随机数进行快速排序 七、主函数 3、概要设计：3.1所需的ADT，每个程序中使用的存储结构设计说明typedef struct int key; ElemType;/元素类型typedef struct ElemType *elem; int length;SqList;/顺序表类型3.2主程序流程以及模块调用关系主函数 main（）五种排序用时的比较，不打印排序后的结果五种排序运行后打印结果Show the menu显示主界面初始化线性表 SqList L; 初始化变量 x,i; ;3.3每个模块的算法设计说明（流程图）3.3.1气泡排序： 开始初始变量 i=1，j=1i小于L.lengt
5、hj小于L.lengthL.elemj.key大于L.elemj+1.key交换第j个和第j+1个元素j+YYY结束N3.3.2直插排序开始初始变量i=2,ji=L.lengthY如果第i位比第i-1位的值小L.elem0.key=L.elemi.keyYj=i-1NN如果第0位比第j位的值小记录后移j=j-1L.elemj+1.key=L.elem0.keyY结束3.3.3选择排序开始初始变量i=1,j,kIlengthJ=i+1Y如果i位置上的值=k位置上的交换数值位置Yj=j+1i=i+1结束NN3.3.4希尔排序开始Y结束N 初始化变量i,d=L.length/2,j,w=0w小于di
6、=1,i小于L.lengthj=i+dJ小于L.length第i个元素大于第j个元素交换第i个元素第j个元素d变为原来的一半YYY3.3.5快速排序开始结束NYY初始化变量pivotkey,low,highLow小于high第high个元素大于pivotkey第low个元素小于pivotkey第low个元素与第high个元素交换第high个元素与第low个元素交换high-Low+Y4、详细设计：4.1函数调用关系图开始界面 各种排序用时比较各排序输出结果起泡排序用时直插排序用时快速排序用时希尔排序用时选择排序用时起泡排序直插排序选择排序希尔排序快速排序5、各个算法实现的源程序：5.1、冒泡排
7、序及其主要算法void qipao(SqList &L)/起泡 start_t=clock(); int i=1,j; while(iL.length) for(j=1;jL.elemj+1.key) L.elem0.key=L.elemj.key; L.elemj.key=L.elemj+1.key; L.elemj+1.key=L.elem0.key; i+;5.2、直接插入排序及其主要算法void InsertSort(SqList &L) /直接插入 start_t=clock(); int i,j; for(i=2;i=L.length;i+) if(L.elemi.key=L.el
8、emi-1.key)/“”，需将L.ri插入有序子序列 L.elem0.key=L.elemi.key; /复制为哨兵 j=i-1; while(L.elem0.keyL.elemj.key) L.elemj+1.key=L.elemj.key; /记录后移 j-; L.elemj+1.key=L.elem0.key; /插入到正确位置 5.3、选择排序及其主要算法void SelectSort(SqList &L)/选择int i,j,k,; for(i=1;iL.length;i+)/选择第i小的记录，并交换到位 for(j=i+1;jL.length;j+) if(L.elemj.key
9、=L.elemk.key) L.elem0.key=L.elemi.key; L.elemi.key=L.elemk.key; L.elemk.key=L.elem0.key;/与第i个记录交换 5.4、希尔排序及其主要算法void xier(SqList &L)/希尔排序并打印结果 start_t=clock(); int i,d=L.length/2,j,w=0,k,yd=0,bj=0; /间长为d while(wd) for(i=1;i=L.length;i+) /第i个与第i+d个相比较 j=i+d; if(jL.elemj.key) k=j; bj+; if(i!=k) L.elem
10、0.key=L.elemi.key;L.elemi.key=L.elemk.key;L.elemk.key=L.elem0.key; d=d/2;/间隔变为原来 的一半 5.5、快速排序及其主要算法int Partition(SqList &L,int low,int high)/快速排序 int pivotkey; L.elem0=L.elemlow; yd1+; pivotkey=L.elemlow.key; /用子表的第一个记录作曲轴记录 while (lowhigh) /从子表的两端交替的向中间扫描 yd1+; while(low=pivotkey) -high; L.elemlow=
11、L.elemhigh; /将比轴记录小的记录交换到低端 while (lowhigh&L.elemlow.key=pivotkey) L.elemhigh=L.elemlow; /将比轴记录大的记录交换到高端 L.elemlow=L.elem0;return low; /返回曲轴所在位置 void QSort(SqList &L,int low,int high) /对顺序表L.rlow.high做快速排序 int pivotloc; int i=1; if(lowhigh) /长度大于一 pivotloc=Partition(L,low,high);/将L.rlow.high一分为二 QSo
12、rt(L,low,pivotloc-1); /对低字表递归排序 QSort(L,pivotloc+1,high); /对高字表递归排序 void QuickSort(SqList &L) /对顺序表L做快速排序 int j; BeforeSort(); QSort(L,1,L.length); for(j=1;j=L.length;j+)printf(%d ,L.elemj); display(yd1,bj1);6、调试分析：1产生随机数2.排序3.汇总7、使用说明：本演示程序对以下5种常用的内部排序算法进行实测比较：起泡排序、直接插入排序、简单选择排序、快速排序、希尔排序。由系统生成30000个随机整数进行比较。程序还可以考虑几组数据的典型性，如：正序、
