内部排序算法实现与性能分析课程设计.

1、目录1、问题描述： 21.1题目内容: 21.2基本要求: 21.3测试数据: 22、需求分析： 22.1程序的基本功能： 22.2输入值、输出值以及输入输出形式： 22.3各个模块的功能要求： 23、概要设计： 33.1所需的ADT每个程序中使用的存储结构设计说明 33.2主程序流程以及模块调用关系 33.3每个模块的算法设计说明（流程图） 43.3.1气泡排序： 43.3.2直插排序 53.3.3选择排序 63.3.4希尔排序 73.3.5快速排序 84、详细设计： 94.1函数调用关系图 95、各个算法实现的源程序： 95.1、冒泡排序及其主要算法 95.2、直接插入排序及其主要算法 1

2、05.3、选择排序及其主要算法 105.4、希尔排序及其主要算法 116、调试分析： 127、使用说明： 138、测试结果： 149、主要参考文献 141、问题描述：1.1题目内容：内部排序算法实现与性能分析1.2基本要求：(1) 数据结构定义(2) 利用随机函数产生30000个随机整数，禾I用插入排序、起泡排序、选 择排序、快速排序、希尔等排序方法进行排序，并统计每一种排序上机所花费的 时间,对各种排序算法做分析比较.1.3测试数据：由函数随机产生的数据，由于是随机产生的，所以在此不一一写出。2、需求分析:2.1程序的基本功能：输入30000个随机整数，对这些数进行多种方法进行排序，并对这些

3、排序做 比较，在屏幕上输出每种排序方法所比较的次数，交换的次数，和时间复杂度。2.2输入值、输出值以及输入输出形式由于程序中所需的数据都是有函数随机生成的整形数，不需要用户自己输 入，用户只需要对演示程序中的一些提示做一些必要的选择以便于程序的执行。程序输出的是对六种排序做的一些比较，即输出六种排序各排序过程中所比 较的数据的个数，交换的数据的次数，和排序完成所用的时间。六种排序依次在 计算机终端上显示，便于用户观察。2.3各个模块的功能要求：一、随机函数：产生随机数二、选择排序函数：对随机数进行选择排序三、起泡排序函数：对随机数进行气泡排序四、直接插入函数：对随机数进行直接插入排序五、希尔排

4、序函数：对随机数进行希尔排序六、快速排序函数：对随机数进行快速排序七、主函数3、概要设计:3.1所需的ADT每个程序中使用的存储结构设计说明typedef structint key;ElemType;元素类型typedef structElemType *elem;in t le ngth;SqList; 顺序表类型3.2主程序流程以及模块调用关系主函数 main （）第18页共14页初始化 变 量x,i;初始化线性表SqListL;Show the menu 显示主 界面五种排 序运行 后打印 结果五种排 序用时 的比较，不打印 排序后 的结果3.3每个模块的算法设计说明（流程图）3.3.

5、1气泡排序：332直插排序333选择排序开始334希尔排序335快速排序4、详细设计：4.1函数调用关系图5、各个算法实现的源程序：5.1、冒泡排序及其主要算法void qipao(SqList &L) 起泡start_t=clock();int i=1,j;while(iL .len gth)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 In sertSort(SqList &L)直接插入sta

6、rt_t=clock();int i,j;for(i=2;i=Len gth;i+)if(L.elemi.key=L.elemi-1.key)“ ”，需将 L.ri插入有序子序列L.elemO.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+

7、) 选择第i小的记录，并交换到位for(j=i+1;jLen gth;j+)if(L.elemj.key=L.elemk.key)L.elemO.key=L.elemi.key;L.elemi.key=L.elemk.key;L.elemk.key=L.elemO.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; / 间长为 dwhile(wd)for(i=1;i=L.length;i+) / 第 i 个与第 i+d 个

8、相比较j=i+d;if(jL.elemj.key)k=j;bj+;if(i!=k)L.elemO.key=L.elemi.key;L.elemi.key=L.elemk.key;L.elemk.key=L.elemO.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+;whi

9、le(low=pivotkey)-high;L.elemlow=L.elemhigh;/将比轴记录小的记录交换到低端while (lowhigh&L.elemlow.key=pivotkey)L.elemhigh=L.elemlow;/将比轴记录大的记录交换到高端L.elemlow=L.elem0;return low;返回曲轴所在位置voidQSort(SqList &L,int low,int high) /对顺序表L.rlow.high做快速排序int pivotloc;/长度大于一将 L.rlow.high 一分为/对低字表递归排序/对高字表递归排序in t i=1;if(lowhig

10、h)pivotloc=Partitio n( L,low,high);QSort(L,low,pivotloc-1);QSort(L,pivotloc+1,high);void QuickSort(SqList &L) /对顺序表L做快速排序 int j;BeforeSort();QSort(L,1 ,L .le ngth); for(j=1;j=Len gth;j+) printf(%d ,L.elemj);display(yd1,bj1);6、调试分析:产生随机数S3224162922913H6103712749423411126.8383l?39fi23B021192S96?241R51

11、211468626S94261332 8481012744149972538324G2129S971534513412341443942 444220745-7S02101513WS217914110296472081V28379&2400JL 3042505丄2505330134377030150017129155116072333G179651957S1366afiiSV?北&目风？4995121H1S3505S8256G776 310523：635643938916231274fl6&608248134-5F72650733235823052711216231 40733212431丄6

12、46丄 84801524203687272 a* ii1B-r *-* 1Iiu-r R-r i*ii f*-* m ii ig-1i1n-r t_r iR RRR IHFHHMidHhRHHRR MHH R M R班级姓名学号算诵0812Q8080326欢迎使用本组数据排序方法比较表 本组数据排序方法比较表 !关键字比校次数!关键字務动坎数I所需时间-.1 .H 快速轴899940001 22423648S 4499550Q129565853 355577672007116224266471 89955 52542 2092749.S3400O1-9710002.8216000.6220BBe.meeeo7、使用说明：本演示程序对以下 5种常用的内部排序算法进行实测比较：起泡排序、直接插入排序、 简单选择排序、快速排序、希尔排序。由系统生成30000个随机整数进行比较。程序还可以考虑几组数据的典型性，女口：正序、逆序和不同程度的乱序。注意采用分块调试的方法。在该程序中可能回有很多让人不满意的地方，我会在以后的学习中逐加改进的。8测试结果:跑：$酸酯划构词增诫品DebuglCppNfe:学号2USU032t欢迎使用去去本组数据耕序方袪比较裘女* 本组数据排序方法比较表 %:所需时何9.8340092.82丄丽0Q.6220B00.0S8