内部排序算法的性能分析
20 / 36
附件
程序清单
/*Config.h*/ /*
* 数据结构课程设计：内部排序算法的性能分析
* 本课程设计为课程研究方便，未使用标准C，未使用标准C部分如： * 直接使用C++的引用，?&?等
* 作者：CSUST 软件班方山城(FSC) */
#ifndef CONFIG_H #define CONFIG_H //避免头文件重复定义
#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
#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