排序方法比较程序的设计与实现程序设计报告.doc

沈阳航空航天大学 课课 程程 设设 计计 报报 告告 课程设计名称：C 语言课程设计语言课程设计 课程设计题目：排序方法比较程序的设计与实现 院（系）：计算机学院 专 业：计算机科学与技术 班 级：1434010105 学 号：143401010518 姓 名：韩冰 指导教师：夏秀峰 完成日期：2015年6月23日 目目 录录 第第 1 章章 概要设计概要设计.1 1.1 题目的内容与要求1 1.2 总体结构1 第第 2 章章 详细设计详细设计.2 2.1 主模块2 2.2 显示模块3 2.3 分词模块3 2.4 替换模块3 第第 3 章章 调试分析调试分析.4 第第 4 章章 使用说明与执行结果使用说明与执行结果.5 参考文献参考文献.7 附附 录（程序清单）录（程序清单）.8 第 1 章 概要设计 1.1 题目的内容与要求题目的内容与要求 课程设计的内容是设计一个比较不同排序方法数据交换次数与数据比较次数 的程序 要求： （1）输入要生成的数据个数，并生成相应数量的随机数 （2）使用不同的排序法对随机数组进行排序。并且比较排序期间数据的交换 次数与比较次数 （3）比较结束后输出结果。结果中包括使用该排序法的交换次数、比较次数 及使用时间 （4）采用 VC 环境进行调试运行。 1.2 总体结构总体结构 本程序主要分为二个模块（模块图见图模块图见图 1.1）：显示模块，排序模块，显示 模块：输入要生成的随机数个数。然后显示选项供用户进行选择。排序模块：根 据用户选择的排序算法。对随机数进行排序。 排序方法比较程序 显 示 模 块 排 序 模 块 图图 1.1 功能模块图功能模块图 第 2 章 详细设计 2.1 主模块主模块 控制整个程序的运行，控制菜单操作，通过主函数模块分别调用各个模块， 实现各项功能，流程如图 2.1 所示。 开始 输入生成随机数个数 random_number 输入相应序号choose选 择功能 使用冒泡排序法排 序并统计比较与交 换次数 使用快速排序法排 序并统计比较与交 换次数 使用插入排序法排 序并统计比较与交 换次数 使用选择排序法排 序并统计比较与交 换次数 输出随机数 Choose=1或 choose=7 Chosse=2或 choose=7 Choose=3或 choose=7 Choose=4或 choose=7 Choose=5 Choose=6 输出结果 Choose=7 Choose!=7 图图 2.1 主模块流程图主模块流程图 注释： 1、输入生成随机数是胡良 2.、无限循环进行，打印主菜单，输入 choose 值，判断，进行各项操作。 2.2 显示模块显示模块 输入生成随机数数量后显示相应功能界面如图 2.2 所示。 Print() 输出欢迎标题 Int random_number; 输入随机数数量 Void print2();/主程序菜单 返回 图图 2.2 显示模块流程图显示模块流程图 注释： 1. 定义变量 random_number 2. 输入随机数数量后输出功能菜单 2.3 排序模块排序模块 输入数据choose 选择排序法冒泡排序法快速排序法插入排序法 Choose=1或 choose=7 Choose=2或 choose=7 Choose=3或 choose=7 Choose=4或 choose=7 图图 2.3 排序模块流程图排序模块流程图 注释： 1、进入功能菜单后输入相应数字 2、根据数字选择排序法进行排序并记录比较与交换次数 第 3 章 调试分析 问题 1： 重新生成随机数时生成的随机数与上一次生成的随机数相同 解决方法： 经过分析这是因为随机数种子默认均为 0 导致的问题。利用 time.h 头文件中的 srand 函数 对随机数种子进行变更达到重复生成不同随机数 问题 2：少量数据计时为 0ms 解决方法：经过分析这是因为进行少量数据排序时 交换次数与比较次数过少导 致运算速度过快。时间不足 1ms 导致。最后利用 windows.h 中的 CPU 时钟频率 相关函数实现以微秒及以上为单位的高精度计时 问题 3：在同一次运行程序 使用两种不同的排序法比较 第二种排序法不存在交 换次数 解决方法：经过检查这是因为经过排序后的数组并没有重置为原来未排序状态， 导致第二个排序法运行时无需排序就得到了正确的顺序 ，最后决定为四种排序 法建立四个存放数据的数组。防止因为使用不同排序法排序相同数组而引发的各 种 bug 问题 4：使用快速排序法时，时间经常十分短暂。并且固定。 解决方法：因为函数内涉及到递归，导致频繁的重置 time 值。最后决定将快速排 序法变为无返回值类型。并且在主函数调用之前和调用之后进行计时。 第 4 章 使用说明与执行结果 此时输入随机数的数量，若输入了范围之外的数据会显示数据错误并要求重新输入 为了体现不同排序法的复杂度差距 我们输入 30000 让程序随机生成 30000 组数据 输入了正确范围的数据 ，显示功能菜单。通过选择不同的序号实现不同排序法的交换次数与 比较次数转换 我们首先选择 5 输出随机数 每排 6 个数字。进行右对齐规范化输出 输出后 sleep4000ms 后继续输出功能菜单 依次输入 1、2、3、4 得到四种排序法的排序结果 每一次输出完数据后都会暂停 4s 后输出主菜单 然后 输入序号 7 进行比较（序号选择顺序随意。进行比较前可以不先运行 因为各功 能独立） 程序会规范化输出四种排序法的比较次数交换次数与使用时间（ms） 。输出结果后会要求重 新数据数量，进行随机数的重新生成 输入 0。直接退出程序。 以下是以 49999 为随机数据数量与以 400 为随机数据数量直接进行的四种排序法的比较结果 参考文献 1Brian W.Kernighan/Dennis M.Ritchie C 程序设计经典M 机械工业出版 社 2014 2杨丽 郭锐 陈雪峰 C 语言程序开发范例经典M 人民邮电出版社 2013 3Ivor Horton C 语言入门经典第五版M 清华大学出版社 4戴艳 零基础学算法 机械工业出版社M 2014 5Mdash 数据结构与算法分析 C 语言描述M 机械工业出版社 2014 6Windows 各种计时函数总结 MoreWindowsS /morewindows/article/details/6854764 附 录（程序清单） #include #include #include/生成随机数时所用随机数种子函数以及时间函数 #include/高精度计时调用winAPI #define random(x) (rand()%x) LARGE_INTEGER nFreq; LARGE_INTEGER nBeginTime; LARGE_INTEGER nEndTime; int main() /*函数声明部分*/ void random_number(int a,int len); /随机数生成函数 void print(); void print2();/功能选择界面 void print_answer(int a, int b, double time); double select_sort(int a, int count, int len); double bubble_sort(int a, int count, int n); void quick_sort(int a, int count, int left, int right); double insert_sort(int a, int count, int len);/四种排序法函数声明 /*变量声明部分*/ int length,choose; int basic_number50000,select_number50000,bubble_number50000,quick_number50000,insert_ number50000; int select_count2 = 0, bubble_count2 = 0 , quick_count2 = 0 , insert_count2 = 0 ; double select_time, bubble_time, quick_time, insert_time; print(); leap: while (1) printf(“请输入数据生成数量(1= 50000 | length 7) printf(“序号输入错误，请重新输入n“); continue; void print() printf(“n 排序方法比较程序的设计与实现n“); printf(“ -143401010518 韩冰nnnn“); void print2() printf(“n请选择您要使用的排序方法n“); printf(“ 1-选择排序法n“); printf(“ 2-冒泡排序法n“); printf(“ 3-快速排序法n“); printf(“ 4-插入排序法n“); printf(“ 5-输出随机数n“); printf(“ 6-重新生成随机数n“); printf(“ 7-四种排序法比较n“); printf(“ 0-退出nnn“); void print_answer(int a,int b,double time) printf(“比较次数:%d 交换次数:%dn“,a,b); printf(“用时%lf msn“,time); void random_number(int a,int len) srand(unsigned int)time(NULL); for (int i = 0;i ai + 1) temp = ai; ai = ai + 1; ai + 1 = temp; change+;/若条件成立进行交换; QueryPerformanceCounter( count0 = compare; count1 = change; return time = (double)(nEndTime.QuadPart - nBeginTime.QuadPart)*1000 / (double)nFreq.QuadPart; void quick_sort(int a, int count, int left, int right)/快速排序法 int i, j, t, temp; if (left right) return;/不能省略 否则无法停止。导致出现堆栈溢出情况 i = left; j = right; temp = aleft; while (i != j) while (aj = temp if (i = 0 k-) ak + 1 = ak; compare+; change+; ak + 1 = t; compare+; QueryPerformanceCounter( count0 = compare; count1 = change; return time = (double)(nEndTime.QuadPart - nBeginTime.QuadPart)*1000 / (double)nFreq.QuadPart; /*以下为标准排版的源代码*/ #include #include #include/生成随机数时所用随机数种子函数以及时间函数 #include/高精度计时调用winAPI #define random(x) (rand()%x) LARGE_INTEGER nFreq; LARGE_INTEGER nBeginTime; LARGE_INTEGER nEndTime; int main() /*函数声明部分*/ void random_number(int a,int len); /随机数生成函数 void print(); void print2();/功能选择界面 void print_answer(int a, int b, double time); double select_sort(int a, int count, int len); double bubble_sort(int a, int count, int n); void quick_sort(int a, int count, int left, int right); double insert_sort(int a, int count, int len);/四种排序法函 数声明 /*变量声明部分*/ int length,choose; int basic_number50000,select_number50000,bubble_number50000,quick_numb er50000,insert_number50000; int select_count2 = 0, bubble_count2 = 0 , quick_count2 = 0 , insert_count2 = 0 ; double select_time, bubble_time, quick_time, insert_time; print(); leap: while (1) printf(“请输入数据生成数量(1= 50000 | length 7) printf(“序号输入错误，请重新输入n“); continue; void print() printf(“n 排序方法比较程序的设计与实现n“); printf(“ -143401010518 韩冰 nnnn“); void print2() printf(“n请选择您要使用的排序方法n“); printf(“ 1-选择排序法n“); printf(“ 2-冒泡排序法n“); printf(“ 3-快速排序法n“); printf(“ 4-插入排序法n“); printf(“ 5-输出随机数n“); printf(“ 6-重新生成随机数n“); printf(“ 7-四种排序法比较n“); printf(“ 0-退出nnn“); void print_answer(int a,int b,double time) printf(“比较次数:%d 交换次数:%dn“,a,b); printf(“用时%lf msn“,time); void random_number(int a,int len) srand(unsigned int)time(NULL); for (int i = 0;i ai + 1) temp = ai; ai = ai + 1; ai + 1 = temp; change+;/若条件成立进行交换; QueryPerformanceCounter( count0 = compare; count1 = change; return time = (double)(nEndTime.QuadPart - nBeginTime.QuadPart)*1000 /