多种排序算法报告.doc

数据结构课程设计多种排序算法比较分析一 目的利用数据结构课程的相关知识完成一个具有一定难度的综合设计题目，利用C/C+语言进行程序设计，并规范地完成课程设计报告。通过课程设计，巩固和加深对线性表、栈、队列、字符串、树、图、查找、排序等理论知识的理解；掌握现实复杂问题的分析建模和解决方法（包括问题描述、系统分析、设计建模、代码实现、结果分析等）；提高利用计算机分析解决综合性实际问题的基本能力。编程实现希尔、快速、堆、归并四种排序算法，并计算每种算法的比较、移动次数。要求待排序数据有系统随机产生，每次选择一种具体的算法将其排序，然后统计排序所需的时间。二 需求分析1、 本程序对以下几种内部排序算法进行实测比较：起泡排序、快速排序、堆排序。2、 程序用来做比较的数据要用伪随机数产生器产生；待排序的元素的为整数；分5组不同的数据，进行不同的测试3、 记录每种算法的每次运行的时间、将每种算法运行的5次时间加和，然后求其平均值4、 以下记录各个函数的大概功能void HeapSort(HeapType *H);该函数将由系统随机产生的数字经堆排序，然后测试其排序所需的时间void HeapAdjust(HeapType *H,int s,int m);该函数将排序后的数据调整void QSort(SqList *L,int low,int high);快速排序函数int Partition(SqList *L,int low,int high);快速排序算法中的具体比较和移动void BubbleSort(SqList *L,int k);起泡排序函数void print(HeapType L);显示每次排序后的每组数字void Initialize(SqList *L);调用该函数将5组的数据填充，数据有系统随机产生void show_time_test();显示每组排序所需要的时间，即显示3种排序方法排序的时间void show_menu();显示可选菜单三 概要设计1、名称: 该程序的主要流程图如下，它简略的描述了程序的大致流程： 开始 输出菜单输入选项判断假 真25431显示时间退出冒泡堆排序快速排序显示完成 结束2、 存储结构:#define MAXSIZE 500 /* 一个用作示例的小顺序表的最大长度 */typedef struct int rMAXSIZE+1; /* r0闲置或用作哨兵单元 */ int length; /* 顺序表长度,除去哨兵的点 */SqList; /* 顺序表类型 */typedef SqList HeapType;该结构体作为存储数据的顺序表，r0作为闲置点，而length作为顺序表的长度其中typedef语句用来声明自定义数据类型Int time_test35= 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0 ;声明3*5的数组，用来存储3种排序算法的5次排序时间3、 冒泡排序算法描述: 两两比较相邻记录的关键码，如果反序则交换，直到没有反序记录为止。实现过程（如图2）。对于数组（21 25 49 16 08）。初态：2125491608第一趟：2125160849第二趟：2116082549第三趟：1608212549第四趟：08162125494、 快速排序算法的大致流程: 首先选择一个基准，将记录分割为两部分，左支小于或等于基准，右支则大于基准，然后对两部分重复上述过程，直至整个序列排序完成。实现过程（如图5）对于数组（21 25 49 16 08）。初态：R0=212125491608highlow第一趟：R0=210825491608highlowR0=210825491625highlowR0=210816491625highlowR0=210816491625lowhigh R0=210816494925highlowR0=21low=high08162149255、关键算法三:实现手动与计算机随机双重输入。手动输入检查程序的正确性，计算机随即输入，可以比较各排序算法的性能。void Rand()/随机数函数鉴于数据较多，让系统随机产生数据，故省略手动输入。6、 关键算法四 : 纠错功能。在用户输入非法数据时，给予警告，并要求用户重新输入，不必重启程序四 详细设计1、随机产生数据，出入5个数组中，为每一种算法提供5组数据:for(i=0;i5;i+) printf(第%d组排序前:n,i+1); Initialize(&Li); printf(n数据产生显示完成，按任意键继续！n);2、菜单显示实现:void show_menu() printf(n请在下列选项中选择一种排序方法或者显示测试时间或者退出); printf(nn 1-堆排序n); printf( 2-快速排序n); printf( 3-冒泡排序n); printf( 4-显示排序时间n); printf( 5-退出n);3、冒泡排序实现:void BubbleSort(SqList *L,int k) int i,j,temp,flag;/定义标志变量、循环控制变量 for(j=1;jk;j+)/外循环 flag=0;/初始标志位 for(i=1;iriL-ri+1)/比较大小 temp=L-ri+1; L-ri+1=L-ri; L-ri=temp; flag=1;/设置标志位 if(flag=0) break;4、快速排序的实现:void QSort(SqList *L,int low,int high)/对顺序表L中的子列表L.rlow.high作快速排序 int pivotloc; if(lowr0=L-rlow; /用子表的第一个记录作为枢纽记录 pivotkey=L-rlow; /枢纽记录关键字 while(lowhigh) /从表的两端交替地向中间扫描 while(lowrhigh=pivotkey) -high; L-rlow=L-rhigh;/将比枢纽记录小的记录移到低端 while(lowrlowrhigh=L-rlow;/将比枢纽记录大的记录移到高端 L-rlow=L-r0; /枢纽记录到位 return low;/返回枢纽位置/* Partition */五 调试分析1、性能分析：n 由于计算机实现的排序算法，没有标准的数据交换操作，因此用交换次数作为衡量性能的标准很不准确，这里计算移动次数，即内存发生赋值操作则计数一次。n 即使计算了内存的拷贝操作，实际的性能仍与很多因素关联，因此，程序作了耗时测试，研究在排序表数据结构发生变化时，算法消耗的时间随之变化的规律。n 数据量对性能的影响：为降低其他因素的影响，每组数据均按比例平均分布。如：100个数据则分布在0，100，500个数据则分布在0，500。理论分析可以得出各种排序算法的时间复杂度和空间复杂度，如下表所示（图6）：2、时间复杂度分析:排序方法平均情况最好情况最坏情况辅助空间直接插入排序O(n2)O(n)O(n2)O(1)起泡排序O(n2)O (n)O(n2)O(1)快速排序O(nlog2n)O(nlog2n)O(n2)O(log2n) O(n)堆排序O(nlogn)O(nlogn)O(nlogn)O(1)3、测试的5组数据:4、界面选择菜单:5、错误的选择或输入不正确的输入项:六 测试结果1、一种算法的5组数据的运行结果的统计:2、三种算法对5组数据的运行结果的统计: 3、运行结果的统计:s如：100个数据则分布在0，100，500个数据则分布在0，500。运行结果：冒泡快速堆比较次数10303750503242625081007647031248500638650788464100014916111191885050001111947461011772210000260988162968255552150004067232517774005062000060688134771655078025000809050474661705064移动次数102419735023313853110050030311835004804210970731000112924688150765000843892857187078100002031866186118422515000325076974592849832000048234213401238842925000659156169596493845七 用户使用说明1、 直接产生数据，有系统产生2、 第二步进入主界面，3、 在界面中选择菜单提供的选择项，若选择错误则提示出错信息，以再一次输入选择项4、 重复上述的过程，在选择菜单是选择不同的，依次将三种算法测试一遍5、 在菜单项中选择选择4即显示排序时间，将三种算法排序的时间显示出来6、 选择6退出程序八 课程设计总结1交换次数统计不够精确。2无论时间还是移动次数，应该有一个对比结果，不能只是罗列出来。3对于快速排序，存在两个问题。其一，不能两边同时进行排序，使得排序趟数增加；其二，没能格式化输出，使得输出不清晰，不美观。4.现四种排序的基本功能，并且测试无误。后来考虑能否优化本程序，首先考虑到测试算法的需求，需要大量随机数，因为增添了随机函数发生函数，满足各种测试条件的需求。之后考虑如何能简化代码以实现多达四种排序算法的简单调用和性能指标统计、算法时间的精确而简易的统计、算法移动次数和比较次数的精确统计。调用精确的系统函数实现时间的统计。此外还添加了一系列优化，使得程序的结构变得更加合理，版面风格也变得好看，可读性增强。5程序的优化是一个艰辛的过程，如果只是实现一般的功能，将变得容易很多，当加上优化，不论是效率还是结构优化，都需要精心设计。这次做优