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

目目 录录 内部排序算法的性能分析内部排序算法的性能分析.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 / 37 1 内部排序算法的性能分析内部排序算法的性能分析 学生姓名：方山城学生姓名：方山城 指导老师：卢曼莎指导老师：卢曼莎 摘摘 要要 在数据结构课程中，内部排序算法是相当重要的一部分，而在实际应 用中，内部排序算法极大地影响着系统资源的分配。在本文中，通过编码用 C 语言实现测试程序对常见的六种排序算法性能从比较次数、移动次数和消耗时 间方面进行了对比，分析数据得出结论，为在实际应用中选择合适排序算法提 供了实验依据。 关键词关键词 内部排序；性能 ；比较次数；移动次数；时间消耗 1 引引 言言 1.1 设计背景设计背景 排序是计算机程序设计中的一种重要操作，它的功能是将一个数据元素 （或记录）的、任意序列，重新排列成一个关键字有序序列。在本学期的数据 结构课程中，排序也是一个重要部分。除了课程学习之外，排序也广泛应用于 数据处理、情报检索、商业金融及企业管理等许多方面。在计算机数据处理中, 特别是在事务处理中,排序占了很大比重,一般认为有 1/4 的时间用在排序上,而对 安装程序,多达 50%的时间花费在对表的排序上1. 在本学期的数据结构课程2中，书上介绍的多种排序算法从算法原理，实现 以及时间复杂度等方面进行了比较详细介绍，但对于各种算法的性能分析仅仅 是停留在时间复杂度层面上，没有比较直观的对常见的六种排序算法性能的对 比，所以，在学习过程中亟需通过实践设计深入的理解各种排序算法性能差异。 内部排序算法的性能分析 2 / 37 2 1.2 设计目的设计目的 加深理解各种数据结构的逻辑结构、存储结构 能熟练掌握各种排序算法的原理和实现 提高 C 语言编程能力，提高动手能力 初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方 法和技能 设计并实现一个能直观反映六种排序算法性能的程序 分析和测试数据得到的结果，得出六种排序算法的性能差异 1.3 设计内容设计内容 涉及算法 排序算法的种类繁多，在本课程设计中选取常用的六种算法进行研究和 设计：直接排序、起泡排序、简单选择排序、快速排序、希尔排序、堆排 序算法。 在今后学习中还可以在本次设计的基础之上增加其他的算法进行 研究分析。 实现功能 如图 1 所示，其中关键字交换记为 3 次移动，时间消耗为基本条件相同 情况下 实现功能 算法的排序演示 各算法性能对比 关键字比较次数 关键字移动次数 时 间 消 耗 图 1 实现功能 内部排序算法的性能分析 3 / 37 3 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+语法，如“引用（/关键字项 InfType otherinfo;/其他数据项 RedType;/记录类型 内部排序算法的性能分析 8 / 37 8 typedef struct SqList RedType rMAXSIZE + 1; /r0闲置或用作哨兵单元 int length;/顺序表长度 SqList;/顺序表类型 3.5 函数接口说明函数接口说明 如表 1 所示为主要函数接口说明 表表 1 1 函数接口说明函数接口说明 所在文件函数名函数功能 InsertSort.cppInsertSort对顺序表 L 作直接插入排序 BubbleSort.cppBubbleSort对顺序表 L 作起泡排序 SSelectSort.cppSSelectSort对顺序表 L 作选择排序 Partition进行一轮含有枢轴的排序 QSort对顺序表 L 中的子序列作快速排序QuickSort.cpp QuickSort对顺序表 L 作快速排序 ProcDlta产生增量序列 ShellInsert对顺序表 L 作一趟希尔插入排序ShellSort.cpp ShellSort对顺序表 L 作希尔排序. HeapAdjust对部分记录进行堆排序 HeapSort.cpp HeapSort对顺序表 H 进行堆排序 Init线性表的初始化 SqList.cpp Output线性表的格式化输出 ShowMenu主菜单 Menu.cpp MainWork主程序控制函数 main.cppTest单个排序函数的测试 内部排序算法的性能分析 9 / 37 9 Compare六种排序算法的对比 Statement程序说明 3.6 功能宏说明功能宏说明 主要功能宏如表 2，详细见程序清单 表表 2 2 主要功能宏说明主要功能宏说明 头文件宏名功能 MAX_SIZE测试数据（即顺序表长）最大值 FUCTION_NUM实现排序功能数 TEST_NUM排序演示测试次数 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.h MOV(a, b)移动 b 记录至 a 记录位置(移动一次） NUM_SIZE关键字的位数（最大范围） LESST(a, b)小于，比较加一 LESSQ(a, b)小于等于，比较加一 MORET(a, b)大于，比较加一 MOREQ(a, b)大于等于，比较加一 KeyType.h PRINT(a)输出关键字 内部排序算法的性能分析 10 / 37 10 RANDMIZE_NUM()产生随机关键字 3.7 性能比较方法性能比较方法 定义静态全局变量无符号整形 cmpcount 统计每次调用排序函数的比较 次数 定义静态全局变量无符号整形 shftcount 统计每次调用排序函数的移动 次数 定义静态全局变量无符号整形 timeuse 统计每次调用排序函数的时间消 耗 定义比较宏每次比较自动统计比较次数（一次）,详见表 2 定义 SWAP 宏每次交换自动统计移动次数（三次）,详见表 2 定义 MOV 宏每次移动自动统计移动次数（一次）,详见表 2 4 详细设计详细设计 4.1 直接排序直接排序 1） 基本思想4 每次都将序列中待排数据插入到之前已经有序的序列中的某个位置， 使新序列依然保持有序。可以从序列的第二个关键字开始，与第一个关 键字比较大小决定顺序再取第三个关键字继续和已经有序的第一、 二 个关键字比较，以此类推。直至整个序列有序。 2） 性能分析4 直接插入排序算法简单， 容易实现。程序有两层循环嵌套，每个 待排数据都要和前面有序的数据作比较，故时间复杂度为 O (n2) ；要 用到 1 个额外存储空间来交换数据。 3） 程序测试 内部排序算法的性能分析 11 / 37 11 图 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 位上。 重复以上过 程，每次的移动都向最终排序的目标前进，直至没有记录需要交换为止。 2） 性能分析4 冒泡排序属于简单的排序，时问性能为 0(n2) ，占用 1 个额外的 存储空间。 3） 程序测试 内部排序算法的性能分析 12 / 37 12 图 6 起泡排序算法演示 4.3 选择排序选择排序 1） 基本思想4 每一趟从待排序数据元素中选出关键字最小的一个元素，与第一个 元素交换位置， 在其余的元素中再找到一个最小的交换到第二个位置， 直到全部待排序的数据元素排完。 2） 性能分析4 简单选择排序只需 1 个额外空间作为交换元素的中间变量；算法由 两层循环嵌套构成，时间复杂度为 O(n2) 。 3） 程序测试 图 7 简单选择算法演示 内部排序算法的性能分析 13 / 37 13 4.4 快速排序快速排序 1） 基本思想5 它是冒泡排序的改进算法，基于分治策略。通过一趟排序将待排记 录分割成独立的两部分，其中一部分记录关键字均比另一部分记录关键 字小，则可分别对这两部分记录继续进行排序，已达到整个序列有序。 2） 性能分析5 若初始记录序列按关键字有序或基本有序时， 快速排序将蜕化为 冒泡排序， 这是最坏的情况。当每次都能将序列恰好分成两个相等序 列时， 出现了快速排序的最佳情况， 此时 n 个关键需要做 log2n 趟排 序，在每一趟中所有划分关键字的和是 n。时间复杂度为 O(n2) 3） 程序测试 图 8 快速排序算法演示 4.5 希尔排序希尔排序 1） 基本思想2 先将整个待排序记录序列分割成为若干个子序列分别进行直接插入 排序，待整个序列中记录“基本有序”时，再对全体记录进行一次直接 插入排序 2） 性能分析2 当增量序列为dltak = 2 (t-k+1) -1,1=k选择排序希尔排序快 速排序堆排序”现象 比较次数上，基本上呈现“插入排序选择排序起泡排序希尔排序快 速排序堆排序”现象 移动次数上，基本上呈现“起泡排序插入排序希尔排序=快速排序堆 排序选择排序”现象 3） 得出结论 a) 各种算法执行时间是待排序长度 n 的函数,并且问题规模越大,时间消耗 越多； b) 待排序长度 n 相同情况下,冒泡排序算法消耗时间最多,堆排序和快速排 序消耗时间最少,即快速排序和堆排序性能最优,而冒泡排序性能最差, 其他算法的时间性能介于他们之间7； c) 排序算法的性能分析和选择是一个复杂而又实际的问题,文中讨论的仅 内部排序算法的性能分析 18 / 37 18 仅是这 6 种排序算法的平均时间性能.在实际应用中,应根据经验和实际 情况合理选择算法.例如,从平均时间性能而言,快速排序是相当快的,其 所需时间最省,但快速排序在最坏情况下的时间性能却不如堆排序和归 并排序.又比如,在插入排序、冒泡排序和选择排序中,以直接插入排序 为最简单,当序列中的记录/基本有序 0 或问题规模 n 较小时,它是最佳 的排序方法.因此常将它和其他的排序方法,诸如快速排序、归并排序等 结合在一起使用3； d) 建立在插入排序基础上的希尔排序和建立在起泡排序基础上的快速排序 的性能表现均比两者中前者强。 e) 综上，当排序长度较大时（上千条） ，且不考虑稳定性的时候，选用快 速排序或堆排序占用的系统资源较少。 6 结束语结束语 通过此次课程设计的实践，感触较深。不仅使我加深了对书本知识的理解， 而且锻炼了我编写程序、调试程序能力，学习文档编写规范，培养独立学习、 吸取他人经验、探索前言知识的习惯。同时，课程设计也充分弥补课堂教学及 普通实验中知识的缺陷。 这次课程设计由于时间有限，对有些地方考虑的还不 够周到，例如有些算法还可以优化，例如冒泡排序，在排序的过程中，各元素 不断接近自己的位置，如果一趟比较下来没有进行过交换，就说明序列有序， 因此要在排序过程中设置一个标志 flag 判断元素是否进行过交换。从而减少不 必要的比较。 在设计的时候，一开始总想到把各种功能都实现，所有的好的东西都去尝 试一遍，后面发现这样子花费的时间实在是太多了（事实上我完成现在的课程 设计花费的时间比起其他的同学来说也算是花费了很多时间了）苦逼的我连续 四天日夜奋战只能看到晚上的月亮早上起来的时候看到的是月亮搞了一天 课程设计出来的时候还是月亮，元旦美好时间在程序猿眼里变得是那么不值得 内部排序算法的性能分析 19 / 37 19 一提了。 编程的时候，我尽量把代码写得尽善尽美，写代码犹如写文章，读代码犹 如读文章，我发现我开始把代码当成是一篇篇美文一首首绝妙的音乐了，是写 出优美动人的文章呢，还是堆砌枯燥乏味的文字，美感就开始在你的代码下面 开始显现出来了，尽管对于这个小程序，无论是标识符的命名，还是宏定义的 实现，我都感觉还很糟糕（或许是这半年来看 Openssl,Gnutls 工程里边代码写 得太漂亮了吧） ，其实一开始，我真不想在程序里面写起满满的注释，注释写着 写着，感觉自己有点白痴了。有些功能我的标识符实在是说得相当清楚了，迫 于老师的硬性要求中文注释不少于 50%，我还是硬着头皮写了满满的注释，可 能是老师跟我认为的不一样觉得写满注释好看些吧。 以前真没有什么概念各种排序算法会在性能上有很大的差距，一想到排序 马上就敲起泡算法了，结果自己的程序告诉我什么起泡冒泡的性能上真是弱爆 了。今后要学点高级点的排序算法，至少起泡算法，我现在是不是很想再用下 去了。 参考文献参考文献 1 殷人昆,陶永雷,盛绚华,等.数据结构(用面向对象方法与 C+描述)M.北 京:清华大学出版社,1999.301. 2 严蔚敏,吴伟民.数据结构(C 语言版) M.北京:清华大学出版社. 2012.548. 3 方 斌,邓丽霞.六种排序算法时间性能的实验分析J. 郧阳师范高等专科学 校学报.2005，23（4）：2324 5 王 莉,各种内部排序算法的比较.科技信息.2012,10（5）：90 6 蒋晓玲,吴瑞红,李相俭,张环冲.常见内部排序算法综述.计算机与网络. 2011,20(2)：220 7申雪琴,内部排序算法的性能分析与探讨J. 河西学院学报.2011，27（5）： 5054 内部排序算法的性能分析 20 / 37 20 附件 程序清单程序清单 /*Config.h*/ /* * 数据结构课程设计：内部排序算法的性能分析 * 本课程设计为课程研究方便，未使用标准C，未使用标准C部分如： * 直接使用C+的引用，/关键字项 InfType otherinfo;/其他数据项 RedType;/记录类型 typedef struct SqList RedType rMAX_SIZE + 1;/r0闲置或用作哨兵单元 int length;/顺序表长度 SqList;/顺序表类型 typedef int Status;/返回状态 static unsigned long cmpcount;/静态全局变量比较次数 static unsigned long shftcount;/静态全局变量移动次数 static double 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 / 37 22 printf( 消耗时间= %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 LIST_MARK_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 SORT_MARK_FSC Status BubbleSort(SqList SORT_MARK_FSC Status SSelectSort(SqList SORT_MARK_FSC Status QuickSort(SqList SORT_MARK_FSC Status ShellSort(SqList SORT_MARK_FSC Status HeapSort(SqList #endif/*Config.h*/ /*KeyType.h*/ #ifndef KEYTYPE_H 内部排序算法的性能分析 23 / 37 23 #define KEYTYPE_H #include #include #define NUM_SIZE 999/关键字的位数（最大范围） #define LESST(a, b) ( (+cmpcount) /关键字类型 typedef char* InfType; #define RANDMIZE_NUM() for (int i = 0; i MAX_SIZE; i+) ri = rand()%NUM_SIZE; /产生随机关键字 #endif/*KeyType.h*/ /*InsertSort.cpp*/ #include Config.h #include KeyType.h extern bool TEST_FSC;/外部标识符，演示排序处使 用 /* * 对顺序表L作插入排序 */ SORT_MARK_FSC Status InsertSort(SqList clock_t start, finish; 内部排序算法的性能分析 24 / 37 24 start = 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);/插入到正确位置 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.h extern bool TEST_FSC;/外部标识符，演示排序处使 用 /* * 对顺序表L作起泡排序 */ SORT_MARK_FSC Status BubbleSort(SqList 内部排序算法的性能分析 25 / 37 25 bool 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 ( MORET(L.rj.key, L.rj+1.key) ) /比较L.rj和L.rj+1 SWAP(L.rj, L.rj+1); /交换L.rj和L.rj+1 flag = true; if ( (TEST_FSC = true) Output(L); if (flag = false) break; L.r0.key = 0; finish = clock(); timeuse = (double)(finish - start) / CLOCKS_PER_SEC;/计算时间 return OK; /*SSelectSort.cpp*/ #include Config.h #include KeyType.h extern bool TEST_FSC;/外部标识符，演示排序处使用 /* * 对顺序表L作选择排序 */ SORT_MARK_FSC Status SSelectSort(SqList 内部排序算法的性能分析 26 / 37 26 clock_t start, finish; start = clock(); 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 = clock(); timeuse = (double)(finish - start) / CLOCKS_PER_SEC; return OK; /*QuickSort.cpp*/ #include Config.h #include KeyType.h extern bool TEST_FSC;/外部标识符，演示排序处使用 int i;/演示次数统计 /* * 交换顺序表中子表L.rlow.high的记录，使枢轴记录到位， * 并返回其所在位置，此时在它之前（后）的记录均不大于(小）于它 */ SUB_SORT_MARK_FSC Status Partition(SqList /用子表的第一个记录作为枢轴记录 while(low high)/从表的两端交替地向中间扫描 while ( (low high) MOV(L.rlow, L.rhigh);/将比枢轴记录小的记录移动到低端 while ( (low high) 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 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 / 37 28 SORT_MARK_FSC Status QuickSort(SqList start = clock(); cmpcount = 0; shftcount= 0; if (TEST_FSC = true) printf(* 排序中 *n); i = 0; QSort(L, 1, L.length, cmpcount, shftcount); finish = clock(); timeuse = (double)(finish - start) / CLOCKS_PER_SEC;/计算时间 return OK; /*ShellSort.cpp*/ #include #include Config.h #include KeyType.h extern bool TEST_FSC;/外部标识符，演示排序处使用 /* * 产生增量序列，dltak = 2 (t-k+1) -1,1=k=t=log2(n+1) */ SUB_SORT_MARK_FSC Status ProcDlta(int * t = int(log(double(MAX_SIZE + 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 / 37 29 /* * 对顺序表L作一趟希尔插入排序. */ SUB_SORT_MARK_FSC Status ShellInsert (SqList for (i = dk+1; i 0 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 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 / 37 30 printf(第%d躺排序., +j); Output(L); finish = clock(); timeuse = (double)(finish - start) / CLOCKS_PER_SEC;/计算时间 return OK; /*HeapSort.cpp*/ #include Config.h #include KeyType.h extern bool TEST_FSC;/外部标识符，演示排序处使用 typedef SqList HeapType;/转换类型 /* * 已知L.rs.m中记录的关键字除L.rs.key之外均满足堆定义，本函数调整L.rs * 的关键字，使H.rs.m成为一个大顶堆（对其中记录的关键字而言） */ SUB_SORT_MARK_FSC Status HeapAdjust(HeapType for(i = 2*s; 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) / CLOCKS_PER_SEC;/计算时间 return OK; /*SqList.cpp*/ #include Config.h #include KeyType.h /* * 线性表的初始化 */ LIST_MARK_FSC Status Init(SqList for (i = 1; i = len; i+) 内部排序算法的性能分析 32 / 37 32 L.ri.key = Ki - 1; L.length = len; return OK; /* * 线性表的格式化输出 */ LIST_MARK_FSC Status Output(SqList 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 / 37 34 case 1: Test(1); break;/插入排序 case 2: Test(2); break;/起泡排序 case 3: Test(3); break;/选择排序 case 4: Test(4); break;/选择排序 case 5: