内部排序算法比较.doc

《内部排序算法比较.doc》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、数据结构课程设计30数据结构课程设计内部排序算法比较目录摘要11绪论12系统分析12.1功能需求12.2数据需求12.3性能需求23总体设计23.1系统设计方案23.2功能模块设计24详细设计34.1数据结构定义34.2伪随机产生数据模块44.3简单选择排序模块64.4起泡排序模块74.5直接插入排序模块84.6希尔排序模块94.7快速排序模块104.8归并排序模块114.9条形图模块125调试与测试135.1调试135.2测试136结论14结束语14参考文献15附录1－用户手册16附录2－源程序18

2、30数据结构课程设计摘要本程序是比较几种排序算法的关键字比较次数和移动次数以取得直观感受。内部算法有冒泡排序、直接插入排序、快速排序、希尔排序、归并排序等。每种算法都有自己的比较方法和优缺点，本程序能更直观的显示出各种排序的比较次数、移动次数和排序时间，并能用条形图（星号表示）进行表示，以便比较各种排序的优劣。该程序运用了数据结构中线性表的顺序存储结构和各种排序算法来共同实现的。关键词：内部排序、条形图。1绪论随着科技的快速发展，越来越多的企业不再浪费人力财力去计算一些统计性结果，而是应用一些简单的程

3、序或系统来完成这些任务。随着学习数据结构课程的深入，了解了不同排序算法的不同排序方法，每种排序对数据的比较次数、移动次数和排序用时都是不同的，本程序实现了六种内部排序算法的比较，并用条形图直观的显示出各种算法的优劣。运用伪随机产生的数据，调用六种排序算法，记录其比较次数、移动次数和排序时间，再分别用条形图（星号表示）表示出来。2系统分析2.1功能需求(1)对起泡排序、直接插入排序、简单选择排序、快速排序、希尔排序、归并排序算法进行比较。(2)待排序的元素的关键字为整数，其中数据要用伪随机产生程序产生，

4、并且至少用5组的输入数据做比较，再使用各种算法对其进行排序，记录其排序时间，再汇总比较。(3)演示程序以人机对话的形式进行，每次测试完毕显示各种比较指标值，比较次数、移动次数和排序时间的列表，并用条形图即星号表示出来，以便比较各种排序的优劣。2.2数据需求抽象数据类型：线性表、排序算法(1)输入数据：需要比较的数据数目30数据结构课程设计(2)输出数据：不同算法的比较次数、移动次数、排序时间的数据以及对应的条形图。2.3性能需求在运行本程序时，只要按照正确的操作方法不会出现无法运行的情况，系统稳定性好

5、，安全，可靠，响应速度由需比较的数字数目多少来决定。3总体设计3.1系统设计方案(1)输入要排序的数据数目(2)抽象数据类型定义typedefstruct{intkey;}ElemType;//关键字typedefstruct{ElemType*elem;intlength;}SqList;//分配顺序存储结构(3)存储结构：本程序采用了线性表的顺序存储结构。(4)算法设计：简单选择排序：运用顺序表。时间复杂度O(n2)，空间复杂度O(1)。起泡排序：时间复杂度O(n2)，空间复杂度O(1)直接插入排

6、序：时间复杂度O(n2)，空间复杂度O(1)希尔排序：时间复杂度O(n1.3)，空间复杂度O(1)快速排序：时间复杂度O(nlog2n)，空间复杂度O(nlog2n)归并排序：时间复杂度O(nlog2n)，空间复杂度O(n)3.2功能模块设计根据分析整个程序主要划分为8个功能模块，分别执行要求中的功能。1个产生伪随机数据模块、6个内部排序算法模块以及1个形成条形图模块。功能模块图如图1所示30数据结构课程设计图1功能模块图(1)伪随机产生数据模块：本程序要求数据是要用伪随机产生程序产生，再用不同排序算

7、法进行排序。(2)简单选择排序模块：运用简单选择排序法对伪随机产生的数据进行排序。(3)起泡排序模块：运用起泡排序法对伪随机产生的数据进行排序。(4)直接插入排序模块：运用直接插入排序法对伪随机产生的数据进行排序。(5)希尔排序模块：运用希尔排序法对伪随机产生的数据进行排序。(6)快速排序：运用快速排序法对伪随机产生的数据进行排序。(7)归并排序：运用归并排序法对伪随机产生的数据进行排序。(8)条形图表示比较结果：统计6种排序算法的比较结果，用条形图表示出来。4详细设计4.1数据结构定义typedef

8、struct{intkey;}ElemType;//关键字30数据结构课程设计typedefstruct{ElemType*elem;intlength;}SqList;//分配顺序存储结构4.2伪随机产生数据模块伪随机产生数据模块可实现伪随机产生不同数目的数据以供排序，运用顺序存储结构来实现的。该模块具体实现程序流程如图2所示。图2伪随机产生数据模块30数据结构课程设计4.3简单选择排序模块简单选择排序模块可实现用简单排序法对产生的数据进行排序。该模块