目 录
内部排序算法的性能分析 .................................................................................... 1 1 引 言 ................................................................................................................ 1 1.1设计背景 .............................................................................................................. 1 1.2设计目的 .............................................................................................................. 2 1.3设计内容 .............................................................................................................. 2 1.4设计过程 .............................................................................................................. 3 1.5编程环境 .............................................................................................................. 3 2 系统功能分析 ................................................................................................... 3 2.1 问题定义 ............................................................................................................. 3 2.2可行性分析 .......................................................................................................... 4 2.3需求分析 .............................................................................................................. 4 3 总体设计 .......................................................................................................... 5 3.1数据流程图 .......................................................................................................... 5 3.2系统总体结构 ...................................................................................................... 6 3.3文件组织结构 ...................................................................................................... 6 3.4数据结构定义 ...................................................................................................... 7 3.5函数接口说明 ...................................................................................................... 8 3.6功能宏说明 .......................................................................................................... 8 3.7性能比较方法 ...................................................................................................... 9 4 详细设计 ......................................................................................................... 10 4.1直接排序 ............................................................................................................ 10 4.2起泡排序 ............................................................................................................ 11 4.3选择排序 ............................................................................................................ 11 4.4快速排序 ............................................................................................................ 12 4.5希尔排序 ............................................................................................................ 13 4.6堆排序 ................................................................................................................ 13 4.7总结和实现 ........................................................................................................ 14 5 系统实现及数据分析 ....................................................................................... 15 5.1系统实现 ............................................................................................................ 15 5.2数据分析 ............................................................................................................ 15 6 结束语 ............................................................................................................. 18 参考文献 ............................................................................................................. 19 程序清单 ............................................................................................................. 20
内部排序算法的性能分析
1 / 36
内部排序算法的性能分析
学生姓名：方山城 指导老师：卢曼莎
摘 要 在数据结构课程中，内部排序算法是相当重要的一部分，而在实际应用中，内部排序算法极大地影响着系统资源的分配。在本文中，通过编码用C语言实现测试程序对常见的六种排序算法性能从比较次数、移动次数和消耗时间方面进行了对比，分析数据得出结论，为在实际应用中选择合适排序算法提供了实验依据。
关键词 内部排序；性能 ；比较次数；移动次数；时间消耗
1 引 言
1.1设计背景
排序是计算机程序设计中的一种重要操作，它的功能是将一个数据元素（或
记录）的、任意序列，重新排列成一个关键字有序序列。在本学期的数据结构课程中，排序也是一个重要部分。除了课程学习之外，排序也广泛应用于数据处理、情报检索、商业金融及企业管理等许多方面。在计算机数据处理中,特别是在事务处理中,排序占了很大比重,一般认为有1/4的时间用在排序上,而对安装程序,多达50%的时间花费在对表的排序上[1].
在本学期的数据结构课程[2]中，书上介绍的多种排序算法从算法原理，实现
以及时间复杂度等方面进行了比较详细介绍，但对于各种算法的性能分析仅仅是停留在时间复杂度层面上，没有比较直观的对常见的六种排序算法性能的对比，所以，在学习过程中亟需通过实践设计深入的理解各种排序算法性能差异。
1
内部排序算法的性能分析
2 / 36
1.2设计目的
? 加深理解各种数据结构的逻辑结构、存储结构 ? 能熟练掌握各种排序算法的原理和实现 ? 提高C语言编程能力，提高动手能力
? 初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法
和技能
? 设计并实现一个能直观反映六种排序算法性能的程序 ? 分析和测试数据得到的结果，得出六种排序算法的性能差异
1.3设计内容
? 涉及算法
排序算法的种类繁多，在本课程设计中选取常用的六种算法进行研究和设计：直接排序、起泡排序、简单选择排序、快速排序、希尔排序、堆排序算法。 在今后学习中还可以在本次设计的基础之上增加其他的算法进行研究分析。 ? 实现功能
如图1所示，其中关键字交换记为3次移动，时间消耗为基本条件相同情况下
算法的排序演示实现功能各算法性能对比关键字比较次数关键字移动次数时 间 消 耗
图1 实现功能
2
内部排序算法的性能分析
3 / 36
1.4设计过程
1) 理论知识学习：本课程设计主要参考长沙理工大学计算机与通信工程学院
2011-2012学年数据结构教材《数据结构(C语言版)》[2],理论知识是一切研究设计的根本，所以扎实基础为研究设计的第一步。根据衡量一个算法时间度量是用时间复杂度,表示为T(n) = O(f(n))它表示算法执行时间是问题规模n的某个函数，执行时间增长率和f(n)增长率相同。所以，此阶段将研究其复杂度问题
2) 分析和撰写文档：按照软件生命周期首先定义并分析内部排序的性能问题，
研究选题各测试程序的可行性后分析相关需求，总体设计测试程序功能后修改并详细设计细节问题，最后编码和测试。在这一整个过程中，撰写相应文字部分，完成本论文的提纲并撰写相应已实现部分。
3) 分析运行结果并得出结论：最后一部分即为编码并测试之后对测试数据的测
试结果进行分析，并得出具有建设性的结论（至少对自己学习数据结构阶段）。并根据结论思考今后编程过程中需要注意的问题。
1.5编程环境
? 软件方面：测试程序在Windows 7下的Visual Studio 2008环境中编写并测试。 ? 硬件方面：测试数据的生成及结果在CPU酷睿i5-2430(双核，2.4GHz,睿频可
达3.0GHz)、GT540(1G独力显存)、4GB内存的微机生成和通过。
? 编程语言：选用语言为C,但测试程序仅作研究演示，不做工程应用，为表达
直观之便，未使用标准C，一些部分借用C++语法，如“引用（&）”功能（这也是教材上使用的方法之一）。
2 系统功能分析
2.1 问题定义
3
内部排序算法的性能分析
4 / 36
在本次课程设计中，正如前面所说的一样，迫切需要一个能实现常用的排序
算法，并对各种排序算法仅仅考虑在相同条件情况下直观地反映排序算法在对比次数、移动次数、时间消耗方面的性能对比。本程序只做排序性能的分析，故人机交换方面要求不高，相关控制用宏实现。
2.2可行性分析
? 技术可行性
本系统采用人机操作进行管理，用Visual Studio 2008进行前台设计、系统随
机数产生数据，用户通过界面操作，系统自动给予合理分析，由于Visual Studio 2008功能强大、使用灵活、良好可扩展性、以及广泛实际应用，充分说明了本系统在技术方面的可行性。 ? 工具可行性
随着计算机的普及，信息时代对软件的应用已不是人们的难题，同时硬件设
备完全能够满足人们的需求，本设计的工具基础详见1.5节，故工具可行性。 ? 经济可行性
这是排序的性能分析系统，投入的人力，财力与物力都是非常小的，只需要
一台电脑，然后安装相应燃尽，故经济上可行。 ? 操作可行性
本系统设计清晰，有良好用户接口，（详见表1），操作简洁，完全可以给用户解决，并达到操作过程中的直观，方便、实用等要求，因此操作方面可行性。
综上，本课程设计可行。
2.3需求分析
任何一个算法在计算机上运行所消耗的时间主要与下面几个因素有关： 第一，算法设计本身的优劣； 第二，问题的规模即原始数据量(n)；
4