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