精品资料（2021-2022年收藏）课程设计报告内部排序算法的性能分析

1、目目 录录内部排序算法的性能分析内部排序算法的性能分析.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

2、.6 堆排序.134.7 总结和实现.145 系统实现及数据分析系统实现及数据分析.155.1 系统实现.155.2 数据分析.156 结束语结束语.18参考文献参考文献.19程序清单程序清单.20内部排序算法的性能分析 1 / 371内部排序算法的性能分析内部排序算法的性能分析学生姓名：方山城学生姓名：方山城 指导老师：卢曼莎指导老师：卢曼莎摘摘 要要 在数据结构课程中，内部排序算法是相当重要的一部分，而在实际应用中，内部排序算法极大地影响着系统资源的分配。在本文中，通过编码用 C语言实现测试程序对常见的六种排序算法性能从比较次数、移动次数和消耗时间方面进行了对比，分析数据得出结论，为在实际

3、应用中选择合适排序算法提供了实验依据。关键词关键词 内部排序；性能 ；比较次数；移动次数；时间消耗1 引引 言言1.1 设计背景设计背景排序是计算机程序设计中的一种重要操作，它的功能是将一个数据元素（或记录）的、任意序列，重新排列成一个关键字有序序列。在本学期的数据结构课程中，排序也是一个重要部分。除了课程学习之外，排序也广泛应用于数据处理、情报检索、商业金融及企业管理等许多方面。在计算机数据处理中,特别是在事务处理中,排序占了很大比重,一般认为有 1/4 的时间用在排序上,而对安装程序,多达 50%的时间花费在对表的排序上1.在本学期的数据结构课程2中，书上介绍的多种排序算法从算法原理，实现

4、以及时间复杂度等方面进行了比较详细介绍，但对于各种算法的性能分析仅仅是停留在时间复杂度层面上，没有比较直观的对常见的六种排序算法性能的对比，所以，在学习过程中亟需通过实践设计深入的理解各种排序算法性能差异。内部排序算法的性能分析 2 / 3721.2 设计目的设计目的加深理解各种数据结构的逻辑结构、存储结构能熟练掌握各种排序算法的原理和实现提高 C 语言编程能力，提高动手能力初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能设计并实现一个能直观反映六种排序算法性能的程序分析和测试数据得到的结果，得出六种排序算法的性能差异1.3 设计内容设计内容 涉及算法排序算法的种类繁多

5、，在本课程设计中选取常用的六种算法进行研究和设计：直接排序、起泡排序、简单选择排序、快速排序、希尔排序、堆排序算法。 在今后学习中还可以在本次设计的基础之上增加其他的算法进行研究分析。 实现功能如图 1 所示，其中关键字交换记为 3 次移动，时间消耗为基本条件相同情况下实现功能算法的排序演示各算法性能对比关键字比较次数关键字移动次数时 间 消 耗图 1 实现功能内部排序算法的性能分析 3 / 3731.4 设计过程设计过程1)理论知识学习：本课程设计主要参考长沙理工大学计算机与通信工程学院2011-2012 学年数据结构教材数据结构(C 语言版)2,理论知识是一切研究设计的根本，所以扎实基础为

6、研究设计的第一步。根据衡量一个算法时间度量是用时间复杂度,表示为 T(n) = O(f(n)它表示算法执行时间是问题规模 n 的某个函数，执行时间增长率和 f(n)增长率相同。所以，此阶段将研究其复杂度问题2)分析和撰写文档：按照软件生命周期首先定义并分析内部排序的性能问题，研究选题各测试程序的可行性后分析相关需求，总体设计测试程序功能后修改并详细设计细节问题，最后编码和测试。在这一整个过程中，撰写相应文字部分，完成本论文的提纲并撰写相应已实现部分。3)分析运行结果并得出结论：最后一部分即为编码并测试之后对测试数据的测试结果进行分析，并得出具有建设性的结论（至少对自己学习数据结构阶段） 。并根

7、据结论思考今后编程过程中需要注意的问题。1.5 编程环境编程环境 软件方面：测试程序在Windows 7下的Visual Studio 2008环境中编写并测试。 硬件方面：测试数据的生成及结果在CPU酷睿i5-2430(双核，2.4GHz,睿频可达3.0GHz)、GT540(1G独力显存)、4GB内存的微机生成和通过。 编程语言：选用语言为C,但测试程序仅作研究演示，不做工程应用，为表达直观之便，未使用标准C，一些部分借用C+语法，如“引用（&） ”功能（这也是教材上使用的方法之一） 。内部排序算法的性能分析 4 / 3742 系统功能分析系统功能分析2.1 问题定义问题定义在本次课

8、程设计中，正如前面所说的一样，迫切需要一个能实现常用的排序算法，并对各种排序算法仅仅考虑在相同条件情况下直观地反映排序算法在对比次数、移动次数、时间消耗方面的性能对比。本程序只做排序性能的分析，故人机交换方面要求不高，相关控制用宏实现。2.2 可行性分析可行性分析 技术可行性本系统采用人机操作进行管理，用 Visual Studio 2008 进行前台设计、系统随机数产生数据，用户通过界面操作，系统自动给予合理分析，由于 Visual Studio 2008 功能强大、使用灵活、良好可扩展性、以及广泛实际应用，充分说明了本系统在技术方面的可行性。 工具可行性随着计算机的普及，信息时代对软件的应

9、用已不是人们的难题，同时硬件设备完全能够满足人们的需求，本设计的工具基础详见 1.5 节，故工具可行性。 经济可行性这是排序的性能分析系统，投入的人力，财力与物力都是非常小的，只需要一台电脑，然后安装相应燃尽，故经济上可行。 操作可行性 本系统设计清晰，有良好用户接口， （详见表 1） ，操作简洁，完全可以给用户解决，并达到操作过程中的直观，方便、实用等要求，因此操作方面可行性。 综上，本课程设计可行。内部排序算法的性能分析 5 / 3752.3 需求分析需求分析任何一个算法在计算机上运行所消耗的时间主要与下面几个因素有关：第一，算法设计本身的优劣；第二，问题的规模即原始数据量(n)；第三，计

10、算机的软硬件配置；第四，大多数算法的时间消耗还与原始数据的初始性质有很大关系.3所以在本次课程设计中，编写符合以下条件的程序进行测试：1） 选用具有常用性的算法和实现方式2）能进行研究对比的数据能在多个数量级上进行3）控制其他变量，仅在同一台微机上得出的数据进行分析4）保证代码的可移植性，并且原始数据的类型可以简单更换5）数据对比清晰直观6） 用户操作界面友好，易于操作3 总体设计总体设计3.1 数据流程图数据流程图如图 2 所示，其中1） 数组 r 和结构体 L 均为存放关键字类型的数据结构2） 原始数据由随机数生成器产生3） 循环次数由相关宏定义实现内部排序算法的性能分析 6 / 376产

11、生随机数数组r结构体L排序演示排序对比循环循环图 2 数据流程图3.2 系统总体结构系统总体结构如图 3 所示，从功能上来看，可以分为排序演示模块和排序对比模块，具体实现的时候可以增加其他辅助功能选择排序模块直接排序模块起泡排序模块快速排序模块希尔排序模块堆排序模块内部排序算法性能分析排序演示模块排序对比模块内部排序算法的性能分析 7 / 377图 3 系统总体结构图3.3 文件组织结构文件组织结构本程序由多文件组成，文件组织结构如图 4 所示Config.hKeyType.hInserSort.cppBubbleSort.cppHeapSort.cppSSlectSort.cppmain.c

12、ppMenu.cppSqList.cppQuickSort.cppShellSort.cpp图 4 文件组织结构图3.4 数据结构定义数据结构定义物理结构定义在文件 Config.htypedef struct RedTypeKeyType key;/关键字项InfType otherinfo;/其他数据项RedType;/记录类型内部排序算法的性能分析 8 / 378typedef struct SqListRedType rMAXSIZE + 1; /r0闲置或用作哨兵单元int length;/顺序表长度SqList;/顺序表类型3.5 函数接口说明函数接口说明如表 1 所示为主要函数接

13、口说明表表 1 1 函数接口说明函数接口说明所在文件函数名函数功能InsertSort.cppInsertSort对顺序表 L 作直接插入排序BubbleSort.cppBubbleSort对顺序表 L 作起泡排序SSelectSort.cppSSelectSort对顺序表 L 作选择排序Partition进行一轮含有枢轴的排序QSort对顺序表 L 中的子序列作快速排序QuickSort.cppQuickSort对顺序表 L 作快速排序ProcDlta产生增量序列ShellInsert对顺序表 L 作一趟希尔插入排序ShellSort.cppShellSort对顺序表 L 作希尔排序.Hea

14、pAdjust对部分记录进行堆排序HeapSort.cppHeapSort对顺序表 H 进行堆排序Init线性表的初始化SqList.cppOutput线性表的格式化输出ShowMenu主菜单Menu.cppMainWork主程序控制函数main.cppTest单个排序函数的测试内部排序算法的性能分析 9 / 379Compare六种排序算法的对比Statement程序说明3.6 功能宏说明功能宏说明主要功能宏如表 2，详细见程序清单表表 2 2 主要功能宏说明主要功能宏说明头文件宏名功能MAX_SIZE测试数据（即顺序表长）最大值FUCTION_NUM实现排序功能数TEST_NUM排序演示测

15、试次数LIST_MARK_FSC顺序表功能函数标志SORT_MARK_FSC排序功能函数标志（入口）SUB_SORT_MARK_FSC排序子函数标志MAIN_PRO_MARK_FSC主函数处理部分函数标志MENU_MARK_FSC菜单函数标志OUTPUT_COUNT(cmpcount,shftcount)格式化输出比较次数和移动次数OUTPUT_TIME(timeuse)格式化输出比较时间SWAP(a, b)交换 a,b 两记录位置（移动三次）Config.hMOV(a, b)移动 b 记录至 a 记录位置(移动一次）NUM_SIZE关键字的位数（最大范围）LESST(a, b)小于，比较加一

16、LESSQ(a, b)小于等于，比较加一MORET(a, b)大于，比较加一MOREQ(a, b)大于等于，比较加一KeyType.hPRINT(a)输出关键字内部排序算法的性能分析 10 / 3710RANDMIZE_NUM()产生随机关键字3.7 性能比较方法性能比较方法定义静态全局变量无符号整形 cmpcount 统计每次调用排序函数的比较次数定义静态全局变量无符号整形 shftcount 统计每次调用排序函数的移动次数定义静态全局变量无符号整形 timeuse 统计每次调用排序函数的时间消耗定义比较宏每次比较自动统计比较次数（一次）,详见表 2定义 SWAP 宏每次交换自动统计移动次数

17、（三次）,详见表 2定义 MOV 宏每次移动自动统计移动次数（一次）,详见表 24 详细设计详细设计4.1 直接排序直接排序1） 基本思想4每次都将序列中待排数据插入到之前已经有序的序列中的某个位置，使新序列依然保持有序。可以从序列的第二个关键字开始，与第一个关键字比较大小决定顺序再取第三个关键字继续和已经有序的第一、 二个关键字比较，以此类推。直至整个序列有序。2） 性能分析4直接插入排序算法简单， 容易实现。程序有两层循环嵌套，每个待排数据都要和前面有序的数据作比较，故时间复杂度为 O (n2) ；要用到 1 个额外存储空间来交换数据。3） 程序测试内部排序算法的性能分析 11 / 371

18、1图 5 直接插入算法演示4.2 起泡排序起泡排序1） 基本思想4一个最简单的交换排序方法是起泡排序法，它和气泡从水中往上冒的情况有些类似。 其具体做法是：对 1 至 n 个记录，先将第 n 个和第n-1 个记录的键值进行比较，如：rn.key rn-1.key，则将两个记录交换。 然后比较第 n-1 个和第 n -2 个记录的关键字；依次类推，直到第2 个记录和第 1 个记录进行比较交换，这称为一趟冒泡。这一趟最明显的效果是：将键值最小的记录传到了第 1 位。然后，对 2 至 n 个记录进行同样操作，则具有次小键值记录被安置在第 2 位上。 重复以上过程，每次的移动都向最终排序的目标前进，直

19、至没有记录需要交换为止。2） 性能分析4冒泡排序属于简单的排序，时问性能为 0(n2) ，占用 1 个额外的存储空间。3） 程序测试 内部排序算法的性能分析 12 / 3712图 6 起泡排序算法演示4.3 选择排序选择排序1） 基本思想4每一趟从待排序数据元素中选出关键字最小的一个元素，与第一个元素交换位置， 在其余的元素中再找到一个最小的交换到第二个位置， 直到全部待排序的数据元素排完。2） 性能分析4 简单选择排序只需 1 个额外空间作为交换元素的中间变量；算法由两层循环嵌套构成，时间复杂度为 O(n2) 。 3） 程序测试图 7 简单选择算法演示内部排序算法的性能分析 13 / 371

20、34.4 快速排序快速排序1） 基本思想5它是冒泡排序的改进算法，基于分治策略。通过一趟排序将待排记录分割成独立的两部分，其中一部分记录关键字均比另一部分记录关键字小，则可分别对这两部分记录继续进行排序，已达到整个序列有序。 2） 性能分析5若初始记录序列按关键字有序或基本有序时， 快速排序将蜕化为冒泡排序， 这是最坏的情况。当每次都能将序列恰好分成两个相等序列时， 出现了快速排序的最佳情况， 此时 n 个关键需要做 log2n 趟排序，在每一趟中所有划分关键字的和是 n。时间复杂度为 O(n2)3） 程序测试图 8 快速排序算法演示4.5 希尔排序希尔排序1） 基本思想2先将整个待排序记录序

21、列分割成为若干个子序列分别进行直接插入排序，待整个序列中记录“基本有序”时，再对全体记录进行一次直接插入排序2） 性能分析2当增量序列为dltak = 2 (t-k+1) -1,1=k=t插入排序选择排序希尔排序快速排序堆排序”现象比较次数上，基本上呈现“插入排序选择排序起泡排序希尔排序快速排序堆排序”现象移动次数上，基本上呈现“起泡排序插入排序希尔排序=快速排序堆排序选择排序”现象3） 得出结论a) 各种算法执行时间是待排序长度 n 的函数,并且问题规模越大,时间消耗越多；b) 待排序长度 n 相同情况下,冒泡排序算法消耗时间最多,堆排序和快速排序消耗时间最少,即快速排序和堆排序性能最优,而

22、冒泡排序性能最差,其他算法的时间性能介于他们之间7；c) 排序算法的性能分析和选择是一个复杂而又实际的问题,文中讨论的仅内部排序算法的性能分析 18 / 3718仅是这 6 种排序算法的平均时间性能.在实际应用中,应根据经验和实际情况合理选择算法.例如,从平均时间性能而言,快速排序是相当快的,其所需时间最省,但快速排序在最坏情况下的时间性能却不如堆排序和归并排序.又比如,在插入排序、冒泡排序和选择排序中,以直接插入排序为最简单,当序列中的记录/基本有序 0 或问题规模 n 较小时,它是最佳的排序方法.因此常将它和其他的排序方法,诸如快速排序、归并排序等结合在一起使用3；d) 建立在插入排序基础

23、上的希尔排序和建立在起泡排序基础上的快速排序的性能表现均比两者中前者强。e) 综上，当排序长度较大时（上千条） ，且不考虑稳定性的时候，选用快速排序或堆排序占用的系统资源较少。6 结束语结束语通过此次课程设计的实践，感触较深。不仅使我加深了对书本知识的理解，而且锻炼了我编写程序、调试程序能力，学习文档编写规范，培养独立学习、吸取他人经验、探索前言知识的习惯。同时，课程设计也充分弥补课堂教学及普通实验中知识的缺陷。 这次课程设计由于时间有限，对有些地方考虑的还不够周到，例如有些算法还可以优化，例如冒泡排序，在排序的过程中，各元素不断接近自己的位置，如果一趟比较下来没有进行过交换，就说明序列有序，

24、因此要在排序过程中设置一个标志 flag 判断元素是否进行过交换。从而减少不必要的比较。 在设计的时候，一开始总想到把各种功能都实现，所有的好的东西都去尝试一遍，后面发现这样子花费的时间实在是太多了（事实上我完成现在的课程设计花费的时间比起其他的同学来说也算是花费了很多时间了）苦逼的我连续四天日夜奋战只能看到晚上的月亮早上起来的时候看到的是月亮搞了一天课程设计出来的时候还是月亮，元旦美好时间在程序猿眼里变得是那么不值得内部排序算法的性能分析 19 / 3719一提了。编程的时候，我尽量把代码写得尽善尽美，写代码犹如写文章，读代码犹如读文章，我发现我开始把代码当成是一篇篇美文一首首绝妙的音乐了，

25、是写出优美动人的文章呢，还是堆砌枯燥乏味的文字，美感就开始在你的代码下面开始显现出来了，尽管对于这个小程序，无论是标识符的命名，还是宏定义的实现，我都感觉还很糟糕（或许是这半年来看 Openssl,Gnutls 工程里边代码写得太漂亮了吧） ，其实一开始，我真不想在程序里面写起满满的注释，注释写着写着，感觉自己有点白痴了。有些功能我的标识符实在是说得相当清楚了，迫于老师的硬性要求中文注释不少于 50%，我还是硬着头皮写了满满的注释，可能是老师跟我认为的不一样觉得写满注释好看些吧。以前真没有什么概念各种排序算法会在性能上有很大的差距，一想到排序马上就敲起泡算法了，结果自己的程序告诉我什么起泡冒泡

26、的性能上真是弱爆了。今后要学点高级点的排序算法，至少起泡算法，我现在是不是很想再用下去了。参考文献参考文献1 殷人昆,陶永雷,盛绚华,等.数据结构(用面向对象方法与 C+描述)M.北京:清华大学出版社,1999.301.2 严蔚敏,吴伟民.数据结构(C 语言版) M.北京:清华大学出版社.2012.548.3 方 斌,邓丽霞.六种排序算法时间性能的实验分析J. 郧阳师范高等专科学校学报.2005，23（4）：23245 王 莉,各种内部排序算法的比较.科技信息.2012,10（5）：906 蒋晓玲,吴瑞红,李相俭,张环冲.常见内部排序算法综述.计算机与网络.2011,20(2)：220 7申雪

27、琴,内部排序算法的性能分析与探讨J. 河西学院学报.2011，27（5）：5054内部排序算法的性能分析 20 / 3720附件 程序清单程序清单/*Config.h*/* * 数据结构课程设计：内部排序算法的性能分析 * 本课程设计为课程研究方便，未使用标准C，未使用标准C部分如： * 直接使用C+的引用，&等 *作者：CSUST 软件班方山城(FSC) */#ifndef CONFIG_H#define CONFIG_H/避免头文件重复定义#include #include #include 内部排序算法的性能分析 21 / 3721#include KeyType.h#defin

28、e MAX_SIZE 8/测试数据（即顺序表长）最大值#define FUCTION_NUM 6/实现排序功能数#define OUTPUT_SIZE 9/控制每行输出个数#define TEST_NUM 4/排序演示测试次数#define OK 1/程序成功返回#define ERROE -1/程序错误返回#define LIST_MARK_FSC/顺序表功能函数标志#define SORT_MARK_FSC/排序功能函数标志（入口）#define SUB_SORT_MARK_FSC/排序子函数标志#define MAIN_PRO_MARK_FSC/主函数处理部分函数标志#define ME

29、NU_MARK_FSC/菜单函数标志typedef struct RedTypeKeyType key;/关键字项InfType otherinfo;/其他数据项RedType;/记录类型typedef struct SqListRedType rMAX_SIZE + 1;/r0闲置或用作哨兵单元int length;/顺序表长度SqList;/顺序表类型typedef int Status;/返回状态static unsigned long cmpcount;/静态全局变量比较次数static unsigned long shftcount;/静态全局变量移动次数static double

30、timeuse;/静态全局变量时间消耗static SqList L;/静态全局变量顺序表static KeyType rMAX_SIZE=49, 38, 65, 97, 76, 13, 27, 49;/随机数产生存放数组，预设处置#define OUTPUT_COUNT(cmpcount, shftcount) printf( 比较次数= %-10d, cmpcount); printf( 移动次数= %-10d, shftcount); /格式化输出比较次数和移动次数#define OUTPUT_TIME(timeuse) 内部排序算法的性能分析 22 / 3722printf( 消耗时间

31、= %fnn, timeuse); /格式化输出比较时间#define SWAP(a, b) shftcount +=3; L.r0 = a; a = b; b = L.r0; /交换a,b两记录位置（移动三次）#define MOV(a, b) shftcount +; a = b; /移动b记录至a记录位置(移动一次）/* * 函数申明部分 * 其中排序函数参数分别为为顺序表，比较次数，移动次数，消耗时间 * 并非所有函数均在此部分申明，只有对外使用接口才申明 */LIST_MARK_FSC Status Init(SqList &, KeyType *, int);LIST_MA

32、RK_FSC Status Output(SqList &);MENU_MARK_FSC void MainWork();MAIN_PRO_MARK_FSC void Compare();MAIN_PRO_MARK_FSC void Test(int);MAIN_PRO_MARK_FSC void Statement();SORT_MARK_FSC Status InsertSort(SqList &,unsigned long &,unsigned long &,double &);SORT_MARK_FSC Status BubbleSort(SqL

33、ist &,unsigned long &,unsigned long &,double &);SORT_MARK_FSC Status SSelectSort(SqList&,unsigned long&,unsigned long &,double &);SORT_MARK_FSC Status QuickSort(SqList&,unsigned long &, unsigned long &, double &);SORT_MARK_FSC Status ShellSort(SqList&a

34、mp;,unsigned long &, unsigned long &, double &);SORT_MARK_FSC Status HeapSort(SqList&,unsigned long &, unsigned long &, double &);#endif/*Config.h*/*KeyType.h*/#ifndef KEYTYPE_H内部排序算法的性能分析 23 / 3723#define KEYTYPE_H#include #include #define NUM_SIZE 999/关键字的位数（最大范围）#defin

35、e LESST(a, b) ( (+cmpcount) & (a) (b) )/小于，比较加一#define LESSQ(a, b) ( (+cmpcount) & (a) (b) )/大于，比较加一#define MOREQ(a, b) ( (+cmpcount) & (a) = (b) )/大于等于，比较加一#define PRINT(a) (printf(%7d, a)/输出关键字typedef int KeyType;/关键字类型typedef char* InfType;#define RANDMIZE_NUM() for (int i = 0; i MAX_

36、SIZE; i+) ri = rand()%NUM_SIZE; /产生随机关键字#endif/*KeyType.h*/*InsertSort.cpp*/#include Config.h#include KeyType.hextern bool TEST_FSC;/外部标识符，演示排序处使用/* * 对顺序表L作插入排序 */SORT_MARK_FSC Status InsertSort(SqList &L, unsigned long &cmpcount, unsigned long &shftcount, double &timeuse)int i,j=0;

37、clock_t start, finish;内部排序算法的性能分析 24 / 3724start = clock();/时间记录cmpcount = 0;shftcount= 0;if (TEST_FSC = true)printf(* 排序中 *n);for (i = 2; i = L.length; i+)if (LESST(L.ri.key, L.ri-1.key)/“”，需将L.ri插入有序表MOV(L.r0, L.ri);/复制为哨兵while (LESST(L.r0.key, L.ri-1.key)MOV(L.ri, L.ri-1);/记录后移i-;MOV(L.ri, L.r0);

38、/插入到正确位置if ( TEST_FSC = true )printf(第%d躺排序., +j);Output(L);finish = clock();timeuse = (double)(finish - start) / CLOCKS_PER_SEC;/计算时间return OK;/*BubbleSort.cpp*/#include Config.h#include KeyType.hextern bool TEST_FSC;/外部标识符，演示排序处使用/* * 对顺序表L作起泡排序 */SORT_MARK_FSC Status BubbleSort(SqList &L, uns

39、igned long &cmpcount, unsigned long &shftcount, double &timeuse)int i, j, k=0;内部排序算法的性能分析 25 / 3725bool flag;clock_t start, finish;start = clock();cmpcount = 0;shftcount= 0;if (TEST_FSC = true)printf(* 排序中 *n);for (i = 1; i L.length; i+)flag = false;for (j = 1; j = L.length - i; j+)if (

40、MORET(L.rj.key, L.rj+1.key) ) /比较L.rj和L.rj+1SWAP(L.rj, L.rj+1); /交换L.rj和L.rj+1flag = true;if ( (TEST_FSC = true) & (flag =true) ) /演示输出 printf(第%d躺排序., +k); Output(L); if (flag = false)break;L.r0.key = 0;finish = clock();timeuse = (double)(finish - start) / CLOCKS_PER_SEC;/计算时间return OK;/*SSelec

41、tSort.cpp*/#include Config.h#include KeyType.hextern bool TEST_FSC;/外部标识符，演示排序处使用/* * 对顺序表L作选择排序 */SORT_MARK_FSC Status SSelectSort(SqList &L, unsigned long &cmpcount, unsigned long &shftcount, double &timeuse)int i, j, k, l=0;内部排序算法的性能分析 26 / 3726clock_t start, finish;start = clock(

42、);cmpcount = 0;shftcount= 0;if (TEST_FSC = true)printf(* 排序中 *n);for (i = 1; i L.length; i+)/选择第i小的记录，并交换位置k = i;for (j = i+1; j = L.length; j+)/选择第i小的记录if ( LESST(L.rj.key, L.rk.key) ) k = j;if (k != i)/与第i个记录交换SWAP(L.ri, L.rk);if ( TEST_FSC = true )printf(第%d躺排序., +l);Output(L);L.r0.key = 0;finish

43、 = clock();timeuse = (double)(finish - start) / CLOCKS_PER_SEC;return OK;/*QuickSort.cpp*/#include Config.h#include KeyType.hextern bool TEST_FSC;/外部标识符，演示排序处使用int i;/演示次数统计/* * 交换顺序表中子表L.rlow.high的记录，使枢轴记录到位， * 并返回其所在位置，此时在它之前（后）的记录均不大于(小）于它 */SUB_SORT_MARK_FSC Status Partition(SqList &L, int l

44、ow, int high, int &pivot, unsigned long &cmpcount, unsigned long 内部排序算法的性能分析 27 / 3727&shftcount)MOV(L.r0, L.rlow);/用子表的第一个记录作为枢轴记录while(low high)/从表的两端交替地向中间扫描while ( (low high) & MOREQ(L.rhigh.key, L.r0.key)high-;MOV(L.rlow, L.rhigh);/将比枢轴记录小的记录移动到低端while ( (low high) & LESSQ(L

45、.rlow.key, L.r0.key)low+;MOV(L.rhigh, L.rlow);/将比枢轴记录大的记录移动到高端MOV(L.rlow, L.r0);/枢轴记录到位pivot = low;/返回枢轴记录位置if ( TEST_FSC = true )/排序演示输出printf(第%d躺排序., +i);Output(L);return OK;/* * 对顺序表L中的子序列L.rlow.high作快速排序 */SUB_SORT_MARK_FSC Status QSort (SqList &L, int low, int high,unsigned long &cmpco

46、unt, unsigned long &shftcount)int pivotloc;if (low high)/长度大于Partition(L, low, high, pivotloc, cmpcount, shftcount); /将L.rlow.high一分为二QSort(L, low, pivotloc-1, cmpcount, shftcount); /对低子表递归排序QSort(L, pivotloc+1, high, cmpcount, shftcount);/对高子表递归排序return OK;/* * 对顺序表L作快速排序 */内部排序算法的性能分析 28 / 372

47、8SORT_MARK_FSC Status QuickSort(SqList &L, unsigned long &cmpcount, unsigned long &shftcount, double &timeuse)clock_t start, finish;start = clock();cmpcount = 0;shftcount= 0;if (TEST_FSC = true)printf(* 排序中 *n);i = 0;QSort(L, 1, L.length, cmpcount, shftcount);finish = clock();timeuse

48、 = (double)(finish - start) / CLOCKS_PER_SEC;/计算时间return OK;/*ShellSort.cpp*/#include #include Config.h#include KeyType.hextern bool TEST_FSC;/外部标识符，演示排序处使用/* * 产生增量序列，dltak = 2 (t-k+1) -1,1=k=t=log2(n+1) */SUB_SORT_MARK_FSC Status ProcDlta(int *&dlta, int &t)int k;t = int(log(double(MAX_SIZ

49、E + 1) / ( log(2.0);dlta = (int *)malloc( (t+1) * sizeof(int);for (k = 1; k = t; k+)dltak = int ( pow(2.0, double(t-k+1) ) ) - 1;return OK;内部排序算法的性能分析 29 / 3729/* * 对顺序表L作一趟希尔插入排序. */SUB_SORT_MARK_FSC Status ShellInsert (SqList &L, int dk, unsigned long &cmpcount, unsigned long &shtfcoun

50、t)int i, j;for (i = dk+1; i 0 & LESST(L.r0.key, L.rj.key); j -= dk)MOV(L.ri, L.ri-dk);/记录后移，查找插入位置i -= dk;MOV(L.ri, L.r0);/插入return OK;/* * 按增量序列dlta0.t-1对顺序表L作希尔排序. */SORT_MARK_FSC Status ShellSort (SqList &L, unsigned long &cmpcount, unsigned long &shtfcount, double &timeuse)in

51、t k,j = 0;int *dlta, t;clock_t start, finish;start = clock();cmpcount = 0;shftcount= 0;if (TEST_FSC = true)printf(* 排序中 *n);ProcDlta(dlta, t); /产生增量序列for (k = 1; k = t; k+)ShellInsert (L, dltak, cmpcount, shtfcount); /一趟增量为dltak的插入排序if ( TEST_FSC = true ) /排序演示输出内部排序算法的性能分析 30 / 3730printf(第%d躺排序.,

52、+j);Output(L);finish = clock();timeuse = (double)(finish - start) / CLOCKS_PER_SEC;/计算时间return OK;/*HeapSort.cpp*/#include Config.h#include KeyType.hextern bool TEST_FSC;/外部标识符，演示排序处使用typedef SqList HeapType;/转换类型/* * 已知L.rs.m中记录的关键字除L.rs.key之外均满足堆定义，本函数调整L.rs * 的关键字，使H.rs.m成为一个大顶堆（对其中记录的关键字而言） */SU

53、B_SORT_MARK_FSC Status HeapAdjust(HeapType &L, int s, int m, unsigned long &cmpcount, unsigned long &shftcount)int i;for(i = 2*s; i = m; i *= 2)/沿key较大的孩子结点向下筛选if (MOREQ(L.rs.key, L.ri.key)/rc应插入在位置s上 break;if (i 0; i-)/把L.r1.H.length表建成大顶堆HeapAdjust(L, i, L.length, cmpcount, shftcount);

54、if (TEST_FSC = true)printf(建成大顶堆.);Output(L);for (i = L.length; i 1; i-)SWAP(L.r1, L.ri);/将对顶记录和当前未经排序子序列L.r1.i/中最后一个记录相互交换HeapAdjust(L, 1, i-1, cmpcount, shftcount);/将L.r1.i-1重新调整为大顶堆if ( TEST_FSC = true )/演示排序printf(第%d躺排序., +j);Output(L);finish = clock();timeuse = (double)(finish - start) / CLOCK

55、S_PER_SEC;/计算时间return OK;/*SqList.cpp*/#include Config.h#include KeyType.h/* * 线性表的初始化 */LIST_MARK_FSC Status Init(SqList &L, KeyType *K, int len)int i;for (i = 1; i = len; i+)内部排序算法的性能分析 32 / 3732L.ri.key = Ki - 1;L.length = len;return OK;/* * 线性表的格式化输出 */LIST_MARK_FSC Status Output(SqList &

56、;L)int i;for (i = 1; i 9 | choice9 | choice1);return choice;/* * 主程序控制函数 */MENU_MARK_FSC void MainWork()int choice, exit= 1;while(exit != 0)system(cls);choice = ShowMenu();/选择、弹出菜单system(cls);switch(choice)内部排序算法的性能分析 34 / 3734case 1: Test(1); break;/插入排序case 2: Test(2); break;/起泡排序case 3: Test(3); break;/选择排序case 4: Test(4); break;/选择排序ca