课程设计报告-内部排序算法的性能分析

《课程设计报告-内部排序算法的性能分析》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、内部排序算法的性能分析35/36目录内部排序算法的性能分析11引言11.1设计背景11.2设计目的21.3设计内容21.4设计过程31.5编程环境32系统功能分析32.1问题定义32.2可行性分析42.3需求分析43总体设计53.1数据流程图53.2系统总体结构63.3文件组织结构63.4数据结构定义73.5函数接口说明83.6功能宏说明83.7性能比较方法94详细设计104.1直接排序104.2起泡排序114.3选择排序114.4快速排序124.5希尔排序134.6堆排序134.7总结和实现145系统实现及数据分析155.1系统实现155.2数据分析156结束语18参考文献19程序清单

2、2035内部排序算法的性能分析35/36内部排序算法的性能分析学生姓名：方山城指导老师：卢曼莎摘要在数据结构课程中，内部排序算法是相当重要的一部分，而在实际应用中，内部排序算法极大地影响着系统资源的分配。在本文中，通过编码用C语言实现测试程序对常见的六种排序算法性能从比较次数、移动次数和消耗时间方面进行了对比，分析数据得出结论，为在实际应用中选择合适排序算法提供了实验依据。关键词内部排序；性能；比较次数；移动次数；时间消耗1引言1.1设计背景排序是计算机程序设计中的一种重要操作，它的功能是将一个数据元素（或记录）的、任意序列，重新排列成一个关键字有序序列。在本学期的数据结构课程中，排序也

3、是一个重要部分。除了课程学习之外，排序也广泛应用于数据处理、情报检索、商业金融及企业管理等许多方面。在计算机数据处理中,特别是在事务处理中,排序占了很大比重,一般认为有1/4的时间用在排序上,而对安装程序,多达50%的时间花费在对表的排序上[1].在本学期的数据结构课程[2]中，书上介绍的多种排序算法从算法原理，实现以及时间复杂度等方面进行了比较详细介绍，但对于各种算法的性能分析仅仅是停留在时间复杂度层面上，没有比较直观的对常见的六种排序算法性能的对比，所以，在学习过程中亟需通过实践设计深入的理解各种排序算法性能差异。35内部排序算法的性能分析35/361.2设计目的Ø加深理解各种数据结

4、构的逻辑结构、存储结构Ø能熟练掌握各种排序算法的原理和实现Ø提高C语言编程能力，提高动手能力Ø初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能Ø设计并实现一个能直观反映六种排序算法性能的程序Ø分析和测试数据得到的结果，得出六种排序算法的性能差异1.3设计内容u涉及算法排序算法的种类繁多，在本课程设计中选取常用的六种算法进行研究和设计：直接排序、起泡排序、简单选择排序、快速排序、希尔排序、堆排序算法。在今后学习中还可以在本次设计的基础之上增加其他的算法进行研究分析。u实现功能如图1所示，其中关键字交换记为3次移动，时间消耗为基本条件相同情况下图1实现功能35内部排序

5、算法的性能分析35/361.4设计过程1)理论知识学习：本课程设计主要参考长沙理工大学计算机与通信工程学院2011-2012学年数据结构教材《数据结构(C语言版)》[2],理论知识是一切研究设计的根本，所以扎实基础为研究设计的第一步。根据衡量一个算法时间度量是用时间复杂度,表示为T(n)=O(f(n))它表示算法执行时间是问题规模n的某个函数，执行时间增长率和f(n)增长率相同。所以，此阶段将研究其复杂度问题2)分析和撰写文档：按照软件生命周期首先定义并分析内部排序的性能问题，研究选题各测试程序的可行性后分析相关需求，总体设计测试程序功能后修改并详细设计细节问题，最后编码和测试。在这一整

6、个过程中，撰写相应文字部分，完成本论文的提纲并撰写相应已实现部分。3)分析运行结果并得出结论：最后一部分即为编码并测试之后对测试数据的测试结果进行分析，并得出具有建设性的结论（至少对自己学习数据结构阶段）。并根据结论思考今后编程过程中需要注意的问题。1.5编程环境u软件方面：测试程序在Windows7下的VisualStudio2008环境中编写并测试。u硬件方面：测试数据的生成及结果在CPU酷睿i5-2430(双核，2.4GHz,睿频可达3.0GHz)、GT540(1G独力显存)、4GB内存的微机生成和通过。u编程语言：选用语言为C,但测试程序仅作研究演示，不做工程应用，为表达直观之便

7、，未使用标准C，一些部分借用C++语法，如“引用（&）”功能（这也是教材上使用的方法之一）。2系统功能分析2.1问题定义35内部排序算法的性能分析35/36在本次课程设计中，正如前面所说的一样，迫切需要一个能实现常用的排序算法，并对各种排序算法仅仅考虑在相同条件情况下直观地反映排序算法在对比次数、移动次数、时间消耗方面的性能对比。本程序只做排序性能的分析，故人机交换方面要求不高，相关控制用宏实现。2.2可行性分析u技术可行性本系统采