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

目 录

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

内部排序算法的性能分析

5 / 36

第三，计算机的软硬件配置；

第四，大多数算法的时间消耗还与原始数据的初始性质有很大关系.[3] 所以在本次课程设计中，编写符合以下条件的程序进行测试： 1） 选用具有常用性的算法和实现方式

2） 能进行研究对比的数据能在多个数量级上进行

3） 控制其他变量，仅在同一台微机上得出的数据进行分析 4） 保证代码的可移植性，并且原始数据的类型可以简单更换 5） 数据对比清晰直观

6） 用户操作界面友好，易于操作

3 总体设计

3.1数据流程图

如图2所示，其中

1） 数组r和结构体L 均为存放关键字类型的数据结构 2） 原始数据由随机数生成器产生 3） 循环次数由相关宏定义实现

产生随机数数组r循环循环结构体L排序演示排序对比

图2 数据流程图

5

内部排序算法的性能分析

6 / 36

3.2系统总体结构

如图3所示，从功能上来看，可以分为排序演示模块和排序对比模块，具体

实现的时候可以增加其他辅助功能

内部排序算法性能分析排序演示模块排序对比模块直接排序模块起泡排序模块选择排序模块快速排序模块希尔排序模块堆排序模块 图3 系统总体结构图

3.3文件组织结构

本程序由多文件组成，文件组织结构如图4所示

6

内部排序算法的性能分析

7 / 36

InserSort.cppKeyType.hBubbleSort.cppQuickSort.cppShellSort.cppSSlectSort.cppConfig.hHeapSort.cppSqList.cppmain.cppMenu.cpp

图4 文件组织结构图

3.4数据结构定义

物理结构定义在文件Config.h typedef struct RedType {

KeyType key;

//关键字项 //其他数据项 //记录类型

InfType otherinfo;

}RedType;

typedef struct SqList {

RedType r[MAXSIZE + 1]; int length;

//r[0]闲置或用作哨兵单元

//顺序表长度 //顺序表类型

}SqList;

7

内部排序算法的性能分析

8 / 36

3.5函数接口说明

如表1 所示为主要函数接口说明

表1 函数接口说明

所在文件 InsertSort.cpp BubbleSort.cpp SSelectSort.cpp 函数名 InsertSort BubbleSort SSelectSort Partition QuickSort.cpp QSort QuickSort ProcDlta ShellSort.cpp ShellInsert ShellSort HeapSort.cpp HeapAdjust HeapSort Init Output ShowMenu MainWork Test main.cpp Compare Statement 函数功能 对顺序表L作直接插入排序 对顺序表L作起泡排序 对顺序表L作选择排序 进行一轮含有枢轴的排序 对顺序表L中的子序列作快速排序 对顺序表L作快速排序 产生增量序列 对顺序表L作一趟希尔插入排序 对顺序表L作希尔排序. 对部分记录进行堆排序 对顺序表H进行堆排序 线性表的初始化 线性表的格式化输出 主菜单 主程序控制函数 单个排序函数的测试 六种排序算法的对比 程序说明 SqList.cpp Menu.cpp

3.6功能宏说明

8

主要功能宏如表2，详细见程序清单

内部排序算法的性能分析

9 / 36

表2 主要功能宏说明

头文件 宏名 MAX_SIZE FUCTION_NUM TEST_NUM LIST_MARK_FSC SORT_MARK_FSC 功能 测试数据（即顺序表长）最大值 实现排序功能数 排序演示测试次数 顺序表功能函数标志 排序功能函数标志（入口） SUB_SORT_MARK_FSC 排序子函数标志 Config.h MAIN_PRO_MARK_FSC 主函数处理部分函数标志 MENU_MARK_FSC OUTPUT_COUNT (cmpcount,shftcount) 菜单函数标志 格式化输出比较次数和移动次数 OUTPUT_TIME(timeuse) 格式化输出比较时间 SWAP(a, b) MOV(a, b) NUM_SIZE LESST(a, b) LESSQ(a, b) KeyType.h MORET(a, b) MOREQ(a, b) PRINT(a) RANDMIZE_NUM() 交换a,b两记录位置（移动三次） 移动b记录至a记录位置(移动一次） 关键字的位数（最大范围） 小于，比较加一 小于等于，比较加一 大于，比较加一 大于等于，比较加一 输出关键字 产生随机关键字 3.7性能比较方法

? 定义静态全局变量无符号整形cmpcount统计每次调用排序函数的比较

次数

? 定义静态全局变量无符号整形shftcount统计每次调用排序函数的移动次

数

9

内部排序算法的性能分析

10 / 36

? 定义静态全局变量无符号整形timeuse统计每次调用排序函数的时间消

耗

? 定义比较宏每次比较自动统计比较次数（一次）,详见表2 ? 定义SWAP宏每次交换自动统计移动次数（三次）,详见表2 ? 定义MOV宏每次移动自动统计移动次数（一次）,详见表2

4 详细设计

4.1直接排序

1） 基本思想[4]

每次都将序列中待排数据插入到之前已经有序的序列中的某个位

置，使新序列依然保持有序。可以从序列的第二个关键字开始，与第一个关键字比较大小决定顺序再取第三个关键字继续和已经有序的第一、 二个关键字比较，以此类推。直至整个序列有序。 2） 性能分析[4]

直接插入排序算法简单， 容易实现。程序有两层循环嵌套，每个待

排数据都要和前面有序的数据作比较，故时间复杂度为O (n2) ；要用到 1个额外存储空间来交换数据。 3） 程序测试

图5 直接插入算法演示

10

内部排序算法的性能分析

11 / 36

4.2起泡排序

1） 基本思想[4]

一个最简单的交换排序方法是起泡排序法，它和气泡从水中往上冒

的情况有些类似。 其具体做法是：对1至n个记录，先将第n个和第n-1个记录的键值进行比较，如：r[n].key < r[n-1].key，则将两个记录交换。 然后比较第n-1个和第n -2个记录的关键字；依次类推，直到第2个记录和第1个记录进行比较交换，这称为一趟冒泡。这一趟最明显的效果是：将键值最小的记录传到了第 1位。然后，对2至n个记录进行同样操作，则具有次小键值记录被安置在第2位上。 重复以上过程，每次的移动都向最终排序的目标前进，直至没有记录需要交换为止。 2） 性能分析[4]

冒泡排序属于简单的排序，时问性能为 0(n2) ，占用 1个额外的存

储空间。 3） 程序测试

图6 起泡排序算法演示

4.3选择排序

1） 基本思想[4]

每一趟从待排序数据元素中选出关键字最小的一个元素，与第一个

元素交换位置， 在其余的元素中再找到一个最小的交换到第二个位置，

11

内部排序算法的性能分析

12 / 36

直到全部待排序的数据元素排完。 2） 性能分析[4]

简单选择排序只需 1个额外空间作为交换元素的中间变量；算法由

两层循环嵌套构成，时间复杂度为O(n2) 。 3） 程序测试

图7 简单选择算法演示

4.4快速排序

1） 基本思想[5]

它是冒泡排序的改进算法，基于分治策略。通过一趟排序将待排记

录分割成独立的两部分，其中一部分记录关键字均比另一部分记录关键字小，则可分别对这两部分记录继续进行排序，已达到整个序列有序。 2） 性能分析[5]

若初始记录序列按关键字有序或基本有序时， 快速排序将蜕化为冒

泡排序， 这是最坏的情况。当每次都能将序列恰好分成两个相等序列时， 出现了快速排序的最佳情况， 此时n个关键需要做log2n趟排序，在每一趟中所有划分关键字的和是n。时间复杂度为O(n2) 3） 程序测试

12

内部排序算法的性能分析

13 / 36

图8 快速排序算法演示

4.5希尔排序

1） 基本思想[2]

先将整个待排序记录序列分割成为若干个子序列分别进行直接插入

排序，待整个序列中记录“基本有序”时，再对全体记录进行一次直接插入排序 2） 性能分析[2]

当增量序列为dlta[k] = 2 ^ (t-k+1) -1,1<=k<=t<=[log2(n+1)]时，时间复

杂度为O(n3/2) 3） 程序测试

图9 希尔排序演示

4.6堆排序

1） 基本思想[2]

先将初始文件建成一个大根堆， 此堆为初始的无序区；再选得一个

13

内部排序算法的性能分析

14 / 36

关键字为最大的记录并与序列中最后一个记录交换，然后对序列中前n-1 个记录进行筛选，重新将它调整为一个“大顶堆”，如此反复直至排序结束。 2） 性能分析

由于它在直接选择排序的基础上利用了比较结果形成， 效率提高很

[2]

大。时间复杂度为O(nlog2n)。 3） 程序测试

图10 堆排序算法演示

4.7总结和实现

? 如表 3所示，对六种排序算法的总结对比

表3 六种排序算法性能对比

排序方法 插入排序 起泡排序 选择排序 快速排序 希尔排序 堆排序 平均时间 O ( n2 / 4 ) O ( n2 ) O ( n2 ) O ( n log n) O ( n2 ) O ( n log n) 最坏情况 O ( n2 ) O ( n2 ) O ( n2 ) O ( n log n) O ( n2 ) O ( n log n) 辅助存储 O(1) O(1) O(1) O (log n) O (1) O (1) ? 详见附件《程序清单》

14

内部排序算法的性能分析

15 / 36

5 系统实现及数据分析

5.1系统实现

? 主界面如图所示

图11 主界面

? 性能对比示例如图所示

图12 性能对比图

5.2数据分析

1） 数据制表

对多组测试结果进行统计得出如下三个表，分别见表4，表5，表6，其中实

15

验中数据全部为随机生成的整数;时间消耗为5次测试平均值,单位为毫秒(ms)。

内部排序算法的性能分析

16 / 36

表4 时间对比结果（单位：毫秒）

排序长度 插入排序 起泡排序 选择排序 希尔排序 快速排序 堆排序 2000 5000 8000 10000 20000 30000 40000 50000 60000 70000 80000 9 67 134 259 848 1925 3516 5570 7879 10730 14560 17 110 258 479 1768 3958 7145 11356 16381 22209 34022 9 55 113 230 692 1604 2849 4479 6608 8807 11393

表5 比较次数

排序长度 插入排序 起泡排序 选择排序 希尔排序 快速排序 100 500 1000 2000 3000 5243 136140 507533 2022071 4518507 4922 124047 498905 1997047 4495799 4950 124750 499500 1999000 4498500

表6 移动次数

排序长度 插入排序 起泡排序 选择排序 希尔排序 快速排序 100 500 1000 2000 2713 68560 254755 1013024 7575 202722 758313 3027120 294 1479 2970 5876 462 2844 6000 12998 462 2844 6000 12998 堆排序 405 2004 4020 4131 5054 111973 420326 1681275 3902350 907 6621 14710 33101 52383 堆排序 205 1020 2045 4131 6093 6 52 99 196 634 1374 2605 3998 5623 7958 10169 0 1 2 2 5 8 11 14 17 25 26 0 0 0 1 1 2 2 3 4 4 5 16

内部排序算法的性能分析

17 / 36

3000 2262239 6768777 8973 20432 20432 11919 2） 数据分析

从 以上表格可以得出以下信息

? 时间消耗上，基本上呈现“起泡排序>插入排序>选择排序>希尔排序>快

速排序>堆排序”现象

? 比较次数上，基本上呈现“插入排序>选择排序>起泡排序>希尔排序>快

速排序>堆排序”现象

? 移动次数上，基本上呈现“起泡排序>插入排序>希尔排序=快速排序>堆

排序>选择排序”现象

3） 得出结论

a) 各种算法执行时间是待排序长度n的函数,并且问题规模越大,时间消耗

越多；

b) 待排序长度n相同情况下,冒泡排序算法消耗时间最多,堆排序和快速排

序消耗时间最少,即快速排序和堆排序性能最优,而冒泡排序性能最差,其他算法的时间性能介于他们之间[7]；

c) 排序算法的性能分析和选择是一个复杂而又实际的问题,文中讨论的仅

仅是这6种排序算法的平均时间性能.在实际应用中,应根据经验和实际情况合理选择算法.例如,从平均时间性能而言,快速排序是相当快的,其所需时间最省,但快速排序在最坏情况下的时间性能却不如堆排序和归并排序.又比如,在插入排序、冒泡排序和选择排序中,以直接插入排序为最简单,当序列中的记录/基本有序0或问题规模n较小时,它是最佳的排序方法.因此常将它和其他的排序方法,诸如快速排序、归并排序等结合在一起使用[3]；

d) 建立在插入排序基础上的希尔排序和建立在起泡排序基础上的快速排序

的性能表现均比两者中前者强。

e) 综上，当排序长度较大时（上千条），且不考虑稳定性的时候，选用快速

排序或堆排序占用的系统资源较少。

17

内部排序算法的性能分析

18 / 36

6 结束语

通过此次课程设计的实践，感触较深。不仅使我加深了对书本知识的理解，

而且锻炼了我编写程序、调试程序能力，学习文档编写规范，培养独立学习、吸取他人经验、探索前言知识的习惯。同时，课程设计也充分弥补课堂教学及普通实验中知识的缺陷。 这次课程设计由于时间有限，对有些地方考虑的还不够周到，例如有些算法还可以优化，例如冒泡排序，在排序的过程中，各元素不断接近自己的位置，如果一趟比较下来没有进行过交换，就说明序列有序，因此要在排序过程中设置一个标志flag判断元素是否进行过交换。从而减少不必要的比较。

在设计的时候，一开始总想到把各种功能都实现，所有的好的东西都去尝试

一遍，后面发现这样子花费的时间实在是太多了（事实上我完成现在的课程设计花费的时间比起其他的同学来说也算是花费了很多时间了）苦逼的我连续四天日夜奋战只能看到晚上的月亮——早上起来的时候看到的是月亮搞了一天课程设计出来的时候还是月亮，元旦美好时间在程序猿眼里变得是那么不值得一提了。

编程的时候，我尽量把代码写得尽善尽美，写代码犹如写文章，读代码犹如

读文章，我发现我开始把代码当成是一篇篇美文一首首绝妙的音乐了，是写出优美动人的文章呢，还是堆砌枯燥乏味的文字，美感就开始在你的代码下面开始显现出来了，尽管对于这个小程序，无论是标识符的命名，还是宏定义的实现，我都感觉还很糟糕（或许是这半年来看Openssl,Gnutls工程里边代码写得太漂亮了吧），其实一开始，我真不想在程序里面写起满满的注释，注释写着写着，感觉自己有点白痴了。有些功能我的标识符实在是说得相当清楚了，迫于老师的硬性要求中文注释不少于50%，我还是硬着头皮写了满满的注释，可能是老师跟我认为的不一样觉得写满注释好看些吧。

以前真没有什么概念各种排序算法会在性能上有很大的差距，一想到排序马

上就敲起泡算法了，结果自己的程序告诉我什么起泡冒泡的性能上真是弱爆了。今后要学点高级点的排序算法，至少起泡算法，我现在是不是很想再用下去了。

18

内部排序算法的性能分析

19 / 36

参考文献

[1] 殷人昆,陶永雷,盛绚华,等.数据结构(用面向对象方法与C++描述)[M].北京:清华大学出版社,1999.301.

[2] 严蔚敏,吴伟民.数据结构(C语言版) [M].北京:清华大学出版社.2012.5～48.

[3] 方 斌,邓丽霞.六种排序算法时间性能的实验分析[J]. 郧阳师范高等专科学校学报.2005，23（4）：23～24

[5] 王 莉,各种内部排序算法的比较.科技信息.2012,10（5）：90

[6] 蒋晓玲,吴瑞红,李相俭,张环冲.常见内部排序算法综述.计算机与网络.2011,20(2)：220

[7]申雪琴,内部排序算法的性能分析与探讨[J]. 河西学院学报.2011，27（5）：50～54

19

内部排序算法的性能分析

20 / 36

附件

程序清单

/*Config.h*/ /*

* 数据结构课程设计：内部排序算法的性能分析

* 本课程设计为课程研究方便，未使用标准C，未使用标准C部分如： * 直接使用C++的引用，?&?等

* 作者：CSUST 软件班方山城(FSC) */

#ifndef CONFIG_H #define CONFIG_H //避免头文件重复定义

#include #include #include #include \

#define 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 MENU_MARK_FSC //菜单函数标志

typedef struct RedType {

KeyType key; //关键字项 InfType otherinfo; //其他数据项 }RedType; //记录类型

typedef struct SqList {

RedType r[MAX_SIZE + 1]; //r[0]闲置或用作哨兵单元

20

内部排序算法的性能分析

21 / 36

int length; //顺序表长度 }SqList; //顺序表类型

typedef int Status; //返回状态

static unsigned long cmpcount; //静态全局变量比较次数 static unsigned long shftcount; //静态全局变量移动次数 static double timeuse; //静态全局变量时间消耗 static SqList L; //静态全局变量顺序表

static KeyType r[MAX_SIZE]={49, 38, 65, 97, 76, 13, 27, 49};

//随机数产生存放数组，预设处置

#define OUTPUT_COUNT(cmpcount, shftcount) { \\ printf(\比较次数= %-10d\, cmpcount); printf(\移动次数= %-10d\, shftcount); \\ } //格式化输出比较次数和移动次数

#define OUTPUT_TIME(timeuse) { \\ printf(\消耗时间= %f\\n\\n\, timeuse); \\ } //格式化输出比较时间

#define SWAP(a, b) { shftcount +=3; L.r[0] = a; a = b; b = L.r[0]; } //交换a,b两记录位置（移动三次）

#define MOV(a, b) { shftcount ++; a = b; } //移动b记录至a记录位置(移动一次） /*

* 函数申明部分

* 其中排序函数参数分别为为顺序表，比较次数，移动次数，消耗时间 * 并非所有函数均在此部分申明，只有对外使用接口才申明 */

LIST_MARK_FSC Status Init(SqList &, KeyType *, int); LIST_MARK_FSC Status Output(SqList &); MENU_MARK_FSC void MainWork(); MAIN_PRO_MARK_FSC void Compare();

21

\\ \\ \\ \\ \\ \\ \\ \\ \\ \\ \\ 内部排序算法的性能分析

22 / 36

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(SqList &,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&,unsigned long &, unsigned long &, double &); SORT_MARK_FSC Status HeapSort(SqList&,unsigned long &, unsigned long &, double &); #endif/*Config.h*/

/*KeyType.h*/ #ifndef KEYTYPE_H #define KEYTYPE_H

#include #include

#define NUM_SIZE 999 //关键字的位数（最大范围）

#define LESST(a, b) ( (++cmpcount) && ((a) < (b)) ) //小于，比较加一

#define LESSQ(a, b) ( (++cmpcount) && ((a) <= (b)) ) //小于等于，比较加一

#define MORET(a, b) ( (++cmpcount) && ((a) > (b)) ) //大于，比较加一

#define MOREQ(a, b) ( (++cmpcount) && ((a) >= (b)) ) //大于等于，比较加一

#define PRINT(a) (printf(\, a)) //输出关键字

typedef int KeyType; //关键字类型

typedef char* InfType;

#define RANDMIZE_NUM() \\ { \\ for (int i = 0; i < MAX_SIZE; i++) \\ r[i] = rand()%NUM_SIZE; \\ } //产生随机关键字

#endif/*KeyType.h*/

22

内部排序算法的性能分析

23 / 36

/*InsertSort.cpp*/ #include \#include \

extern bool TEST_FSC; //外部标识符，演示排序处使用 /*

* 对顺序表L作插入排序 */

SORT_MARK_FSC Status InsertSort(SqList &L, unsigned long &cmpcount, unsigned long &shftcount, double &timeuse) {

int i,j=0;

clock_t start, finish;

start = clock(); //时间记录 cmpcount = 0; shftcount= 0;

if (TEST_FSC == true)

printf(\排序中 ***\\n\); for (i = 2; i <= L.length; i++) {

if (LESST(L.r[i].key, L.r[i-1].key)) //“<”，需将L.r[i]插入有序表

{

MOV(L.r[0], L.r[i]); //复制为哨兵 while (LESST(L.r[0].key, L.r[i-1].key)) {

MOV(L.r[i], L.r[i-1]); //记录后移 i--; }

MOV(L.r[i], L.r[0]); //插入到正确位置 if ( TEST_FSC == true ) {

printf(\第%d躺排序...\, ++j); Output(L); } } }

finish = clock();

timeuse = (double)(finish - start) / CLOCKS_PER_SEC;//计算时间 return OK; }

23

内部排序算法的性能分析

24 / 36

/*BubbleSort.cpp*/ #include \#include \

extern bool TEST_FSC; //外部标识符，演示排序处使用 /*

* 对顺序表L作起泡排序 */

SORT_MARK_FSC Status BubbleSort(SqList &L, unsigned long &cmpcount, unsigned long &shftcount, double &timeuse) {

int i, j, k=0; 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.r[j].key, L.r[j+1].key) ) //比较L.r[j]和L.r[j+1] {

SWAP(L.r[j], L.r[j+1]); //交换L.r[j]和L.r[j+1] flag = true; } }

if ( (TEST_FSC == true) && (flag ==true) ) //演示输出 {

printf(\第%d躺排序...\, ++k); Output(L); }

if (flag == false) break; }

L.r[0].key = 0; finish = clock();

timeuse = (double)(finish - start) / CLOCKS_PER_SEC;//计算时间 return OK; }

24

内部排序算法的性能分析

25 / 36

/*SSelectSort.cpp*/ #include \#include \

extern 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;

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.r[j].key, L.r[k].key) ) {

k = j; } }

if (k != i) //与第i个记录交换 {

SWAP(L.r[i], L.r[k]); if ( TEST_FSC == true ) {

printf(\第%d躺排序...\, ++l); Output(L); } } }

L.r[0].key = 0; finish = clock();

timeuse = (double)(finish - start) / CLOCKS_PER_SEC; return OK; }

25

内部排序算法的性能分析

26 / 36

/*QuickSort.cpp*/ #include \#include \

extern bool TEST_FSC; //外部标识符，演示排序处使用 int i; //演示次数统计 /*

* 交换顺序表中子表L.r[low..high]的记录，使枢轴记录到位，

* 并返回其所在位置，此时在它之前（后）的记录均不大于(小）于它 */

SUB_SORT_MARK_FSC Status Partition(SqList &L, int low, int high, int &pivot, unsigned long &cmpcount, unsigned long &shftcount) {

MOV(L.r[0], L.r[low]); //用子表的第一个记录作为枢轴记录 while(low < high) //从表的两端交替地向中间扫描 {

while ( (low < high) && MOREQ(L.r[high].key, L.r[0].key)) high--;

MOV(L.r[low], L.r[high]); //将比枢轴记录小的记录移动到低端

while ( (low < high) && LESSQ(L.r[low].key, L.r[0].key)) low++;

MOV(L.r[high], L.r[low]); //将比枢轴记录大的记录移动到高端 }

MOV(L.r[low], L.r[0]); //枢轴记录到位 pivot = low; //返回枢轴记录位置 if ( TEST_FSC == true ) //排序演示输出 {

printf(\第%d躺排序...\, ++i); Output(L); }

return OK; } /*

* 对顺序表L中的子序列L.r[low..high]作快速排序 */

SUB_SORT_MARK_FSC Status QSort (SqList &L, int low, int high,

unsigned long &cmpcount, unsigned long &shftcount) {

int pivotloc;

if (low < high) //长度大于 {

Partition(L, low, high, pivotloc, cmpcount, shftcount);

26

内部排序算法的性能分析

27 / 36

//将L.r[low..high]一分为二 QSort(L, low, pivotloc-1, cmpcount, shftcount); //对低子表递归排序 QSort(L, pivotloc+1, high, cmpcount, shftcount);//对高子表递归排序 }

return OK; } /*

* 对顺序表L作快速排序 */

SORT_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 = (double)(finish - start) / CLOCKS_PER_SEC; //计算时间 return OK; }

/*ShellSort.cpp*/ #include #include \#include \

extern bool TEST_FSC; //外部标识符，演示排序处使用 /*

* 产生增量序列，dlta[k] = 2 ^ (t-k+1) -1,1<=k<=t<=[log2(n+1)] */

27

内部排序算法的性能分析

28 / 36

SUB_SORT_MARK_FSC Status ProcDlta(int *&dlta, int &t) {

int k;

t = int((log(double(MAX_SIZE + 1))) / ( log(2.0))); dlta = (int *)malloc( (t+1) * sizeof(int)); for (k = 1; k <= t; k++) {

dlta[k] = int ( pow(2.0, double(t-k+1) ) ) - 1; }

return OK; } /*

* 对顺序表L作一趟希尔插入排序. */

SUB_SORT_MARK_FSC Status ShellInsert (SqList &L, int dk, unsigned long &cmpcount, unsigned long &shtfcount) {

int i, j;

for (i = dk+1; i <= L.length; i++) {

if (LESST(L.r[i].key, L.r[i-dk].key)) //需将L.r[i]插入到有序增量子表 {

MOV(L.r[0], L.r[i]); //暂存在L.r[0]

for (j = i-dk; j>0 && LESST(L.r[0].key, L.r[j].key); j -= dk) {

MOV(L.r[i], L.r[i-dk]); //记录后移，查找插入位置 i -= dk; }

MOV(L.r[i], L.r[0]); //插入 } }

return OK; } /*

* 按增量序列dlta[0...t-1]对顺序表L作希尔排序. */

SORT_MARK_FSC Status ShellSort (SqList &L, unsigned long &cmpcount, unsigned long &shtfcount, double &timeuse) {

int k,j = 0; int *dlta, t;

clock_t start, finish;

28

内部排序算法的性能分析

29 / 36

start = clock(); cmpcount = 0; shftcount= 0;

if (TEST_FSC == true)

printf(\排序中 ***\\n\);

ProcDlta(dlta, t); //产生增量序列 for (k = 1; k <= t; k++)

ShellInsert (L, dlta[k], cmpcount, shtfcount);

//一趟增量为dlta[k]的插入排序 if ( TEST_FSC == true ) //排序演示输出 {

printf(\第%d躺排序...\, ++j); Output(L); }

finish = clock();

timeuse = (double)(finish - start) / CLOCKS_PER_SEC;//计算时间 return OK; }

/*HeapSort.cpp*/ #include \#include \

extern bool TEST_FSC; //外部标识符，演示排序处使用 typedef SqList HeapType; //转换类型 /*

* 已知L.r[s...m]中记录的关键字除L.r[s].key之外均满足堆定义，本函数调整L.r[s] * 的关键字，使H.r[s...m]成为一个大顶堆（对其中记录的关键字而言） */

SUB_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.r[s].key, L.r[i].key)) //rc应插入在位置s上 break;

if ((i < m) && (LESST(L.r[i].key, L.r[i+1].key)) )

//j为key较大的记录的下表

29

内部排序算法的性能分析

30 / 36

i++;

SWAP(L.r[s], L.r[i]); //插入 }

return OK; } /*

* 对顺序表H进行堆排序 */

SORT_MARK_FSC Status HeapSort (HeapType &L, unsigned long &cmpcount, unsigned long &shftcount, double &timeuse) {

int i,j = 0;

clock_t start, finish; start = clock(); cmpcount = 0; shftcount= 0;

if (TEST_FSC == true)

printf(\排序中 ***\\n\);

for (i = L.length/2; i > 0; i--) //把L.r[1..H.length]表建成大顶堆 HeapAdjust(L, i, L.length, cmpcount, shftcount);

if (TEST_FSC == true) {

printf(\建成大顶堆...\); Output(L); }

for (i = L.length; i > 1; i--) {

SWAP(L.r[1], L.r[i]); //将对顶记录和当前未经排序子序列L.r[1..i] //中最后一个记录相互交换 HeapAdjust(L, 1, i-1, cmpcount, shftcount);

//将L.r[1..i-1]重新调整为大顶堆 if ( TEST_FSC == true ) //演示排序 {

printf(\第%d躺排序...\, ++j); Output(L); } }

finish = clock();

timeuse = (double)(finish - start) / CLOCKS_PER_SEC;//计算时间 return OK; }

30

内部排序算法的性能分析

31 / 36

/*SqList.cpp*/

#include \#include \ /*

* 线性表的初始化 */

LIST_MARK_FSC Status Init(SqList &L, KeyType *K, int len) {

int i;

for (i = 1; i <= len; i++) {

L.r[i].key = K[i - 1]; }

L.length = len; return OK; } /*

* 线性表的格式化输出 */

LIST_MARK_FSC Status Output(SqList &L) {

int i;

for (i = 1; i <= L.length; i++) {

PRINT(L.r[i].key); if (i%OUTPUT_SIZE == 0) {

printf(\); } }

printf(\); return OK; }

31

//输出关键字

//控制每行输出个数 内部排序算法的性能分析

32 / 36

/*Menu.cpp*/

#include \/*

* 主菜单 */

MENU_MARK_FSC int ShowMenu() {

int choice;

printf(\※※※※※※※※※※※※※※※※※※※※※※※※※※※※※※※※n\); printf(\※************************************************************※\\n\); printf(\※* 内部排序算法的性能分析 *※\\n\); printf(\※* *※\\n\); printf(\※* 作者：软件班方山城（FSC) *※\\n\); printf(\※* Mounty_FSC *※\\n\); printf(\※************************************************************※\\n\); printf(\※* *※\\n\); printf(\※* （1）插入排序算法测试 （2）起泡排序算法测试 *※\\n\); printf(\※* （3）选择排序算法测试 （4）快速排序算法测试 *※\\n\); printf(\※* （5）希尔排序算法测试 （6）堆 排序算法测试 *※\\n\); printf(\※* （7）内部排序算法比较 *※\\n\); printf(\※* （8）软件 使用 说明 （9）退 出 程 序 *※\\n\); printf(\※* *※\\n\);printf(\※* 请按键选择...... *※\\n\); printf(\※************************************************************※\\n\); printf(\※※※※※※※※※※※※※※※※※※※※※※※※※※※※※※※※\\n\);

do {

printf(\); scanf(\, &choice); getchar();

if(choice>9 || choice<1) {

printf(\输入错误！请重新输入！\\n\);

}

}while(choice>9 || choice<1); return choice; } /*

* 主程序控制函数 */

MENU_MARK_FSC void MainWork()

32

内部排序算法的性能分析

33 / 36

{

int choice, exit= 1; while(exit != 0) {

system(\);

choice = ShowMenu(); //选择、弹出菜单 system(\); switch(choice) {

case 1: {Test(1); break;} //插入排序 case 2: {Test(2); break;} //起泡排序 case 3: {Test(3); break;} //选择排序 case 4: {Test(4); break;} //选择排序 case 5: {Test(5); break;} //快速排序 case 6: {Test(6); break;} //希尔排序 case 7: {Compare(); break;} //排序比较 case 8: {Statement(); break;} //程序说明 case 9: {exit = 0; break;} //退出程序 } } }

/* main.cpp */ #include \#include \bool TEST_FSC; /*

* 单个排序函数的测试 */

MAIN_PRO_MARK_FSC void Test(int k) {

TEST_FSC = true; int i;

for (i = 0; i < TEST_NUM; i++) {

RANDMIZE_NUM();

Init(L, r, MAX_SIZE); printf(\NO.%d TEST ************* 排序前 ****************\\n\, i+1);

Output(L);

33

内部排序算法的性能分析

34 / 36

switch(k) {

case 1: InsertSort(L, cmpcount, shftcount, timeuse); break; case 2: BubbleSort(L, cmpcount, shftcount, timeuse); break; case 3: SSelectSort(L, cmpcount, shftcount, timeuse); break; case 4: QuickSort(L, cmpcount, shftcount, timeuse); break; case 5: ShellSort(L, cmpcount, shftcount, timeuse); break; case 6: HeapSort(L, cmpcount, shftcount, timeuse); break; }

printf(\排序后 ***\\n\); Output(L);

printf(\); }

TEST_FSC = 0; system(\); } /*

* 六种排序算法的对比 */

MAIN_PRO_MARK_FSC void Compare() {

int i;

/**************** Fuction为函数指针数组*******************/

Status(*Fuction[FUCTION_NUM])(SqList &,unsigned long &,unsigned long &,double &);

Fuction[0] = InsertSort; Fuction[1] = BubbleSort; Fuction[2] = SSelectSort; Fuction[3] = QuickSort; Fuction[4] = ShellSort; Fuction[5] = HeapSort;

/**************** name为函数名数组*******************/

char name[FUCTION_NUM][12]={\插入排序\,\起泡排序\,\选择排序\, \快速排序\,\希尔排序\,\堆排序\}; RANDMIZE_NUM();

printf(\线性表长度为%d--------------------\\n\\n\, MAX_SIZE); for (i = 0; i < FUCTION_NUM; i++) {

printf(\, name[i]); Init(L, r, MAX_SIZE);

(*Fuction[i])(L, cmpcount, shftcount, timeuse); OUTPUT_COUNT(cmpcount, shftcount);

34

内部排序算法的性能分析

35 / 36

OUTPUT_TIME(timeuse); }

system(\); } /*

* 程序说明 */

MAIN_PRO_MARK_FSC void Statement() {

printf(\用户手册---------------------------\\n\); printf(\作者：CSUST 软件班方山城(FSC)\\n\\n\); printf(\主菜单~6选项为相关排序算法的测试功能\\n\\n\);

printf(\主菜单第项前六种算法的性能对比，其间有如几点说明：\\n\); printf(\希尔排序的增量为教科书上介绍的方法： dlta[k]=2^(t-k+1)-1,t=[log2(n+1)]\\n\\n\); printf(\本程序只做排序性能的分析，故人机交换方面要求不高，相关控制用宏实现\\n\);

printf(\什么宏什么功能\\n\\n\);

printf(\由于课程时间有限，程序健壮性不足，但功能均已实现。未处理异常抛出，但是从Status可以看出空间来处理\\n\\n\);

printf(\); system(\); }

MAIN_PRO_MARK_FSC void main() {

MainWork(); }

35

内部排序算法的性能分析

35 / 36

OUTPUT_TIME(timeuse); }

system(\); } /*

* 程序说明 */

MAIN_PRO_MARK_FSC void Statement() {

printf(\用户手册---------------------------\\n\); printf(\作者：CSUST 软件班方山城(FSC)\\n\\n\); printf(\主菜单~6选项为相关排序算法的测试功能\\n\\n\);

printf(\主菜单第项前六种算法的性能对比，其间有如几点说明：\\n\); printf(\希尔排序的增量为教科书上介绍的方法： dlta[k]=2^(t-k+1)-1,t=[log2(n+1)]\\n\\n\); printf(\本程序只做排序性能的分析，故人机交换方面要求不高，相关控制用宏实现\\n\);

printf(\什么宏什么功能\\n\\n\);

printf(\由于课程时间有限，程序健壮性不足，但功能均已实现。未处理异常抛出，但是从Status可以看出空间来处理\\n\\n\);

printf(\); system(\); }

MAIN_PRO_MARK_FSC void main() {

MainWork(); }

35

本文来源：https://www.bwwdw.com/article/x7va.html