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