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

1、I / 23 文档可自由编辑打印沈阳航空航天大学课课 程程 设设 计计 报报 告告课程设计名称：C 语言课程设计语言课程设计课程设计题目：排序方法比较程序的设计与实现院（系）：计算机学院专 业：计算机科学与技术班 级：1434010105学 号：143401010518姓 名：韩冰指导教师：夏秀峰完成日期：2015年6月23日I / 23 文档可自由编辑打印目目 录录第第 1 章章 概要设计概要设计.11.1 题目的内容与要求.11.2 总体结构.1第第 2 章章 详细设计详细设计.22.1 主模块.22.2 显示模块.32.3 分词模块.32.4 替换模块.3第第 3 章章 调试分析调试分析

2、.4第第 4 章章 使用说明与执行结果使用说明与执行结果.5参考文献参考文献.7附附 录（程序清单）录（程序清单）.81 / 23 文档可自由编辑打印第 1 章 概要设计1.1 题目的内容与要求题目的内容与要求课程设计的内容是设计一个比较不同排序方法数据交换次数与数据比较次数的程序要求： （1）输入要生成的数据个数，并生成相应数量的随机数（2）使用不同的排序法对随机数组进行排序。并且比较排序期间数据的交换次数与比较次数（3）比较结束后输出结果。结果中包括使用该排序法的交换次数、比较次数及使用时间（4）采用 VC 环境进行调试运行。1.2 总体结构总体结构本程序主要分为二个模块（模块图见图模块图

3、见图 1.1）：显示模块，排序模块，显示模块：输入要生成的随机数个数。然后显示选项供用户进行选择。排序模块：根据用户选择的排序算法。对随机数进行排序。排序方法比较程序显 示 模 块排 序 模 块图图 1.1 功能模块图功能模块图2 / 23 文档可自由编辑打印第 2 章 详细设计2.1 主模块主模块控制整个程序的运行，控制菜单操作，通过主函数模块分别调用各个模块，实现各项功能，流程如图 2.1 所示。开始输入生成随机数个数random_number输入相应序号choose选择功能使用冒泡排序法排序并统计比较与交换次数使用快速排序法排序并统计比较与交换次数使用插入排序法排序并统计比较与交换次数使

4、用选择排序法排序并统计比较与交换次数输出随机数Choose=1或choose=7Chosse=2或choose=7Choose=3或choose=7Choose=4或choose=7Choose=5Choose=6输出结果Choose=7Choose!=7图图 2.1 主模块流程图主模块流程图注释：1、输入生成随机数是胡良2.、无限循环进行，打印主菜单，输入 choose 值，判断，进行各项操作。2.2 显示模块显示模块输入生成随机数数量后显示相应功能界面如图 2.2 所示。3 / 23 文档可自由编辑打印Print()输出欢迎标题Int random_number;输入随机数数量Void p

5、rint2();/主程序菜单返回图图 2.2 显示模块流程图显示模块流程图注释：1. 定义变量 random_number2. 输入随机数数量后输出功能菜单4 / 23 文档可自由编辑打印2.3 排序模块排序模块输入数据choose选择排序法冒泡排序法快速排序法插入排序法Choose=1或choose=7Choose=2或choose=7Choose=3或choose=7Choose=4或choose=7图图 2.3 排序模块流程图排序模块流程图注释：1、进入功能菜单后输入相应数字2、根据数字选择排序法进行排序并记录比较与交换次数5 / 23 文档可自由编辑打印第 3 章 调试分析问题 1：重

6、新生成随机数时生成的随机数与上一次生成的随机数相同解决方法：经过分析这是因为随机数种子默认均为 0 导致的问题。利用 time.h 头文件中的srand 函数 对随机数种子进行变更达到重复生成不同随机数问题 2：少量数据计时为 0ms解决方法：经过分析这是因为进行少量数据排序时 交换次数与比较次数过少导致运算速度过快。时间不足 1ms 导致。最后利用 windows.h 中的 CPU 时钟频率相关函数实现以微秒及以上为单位的高精度计时问题 3：在同一次运行程序 使用两种不同的排序法比较 第二种排序法不存在交换次数解决方法：经过检查这是因为经过排序后的数组并没有重置为原来未排序状态，导致第二个排

7、序法运行时无需排序就得到了正确的顺序 ，最后决定为四种排序法建立四个存放数据的数组。防止因为使用不同排序法排序相同数组而引发的各种 bug问题 4：使用快速排序法时，时间经常十分短暂。并且固定。解决方法：因为函数内涉及到递归，导致频繁的重置 time 值。最后决定将快速排序法变为无返回值类型。并且在主函数调用之前和调用之后进行计时。6 / 23 文档可自由编辑打印第 4 章 使用说明与执行结果 此时输入随机数的数量，若输入了范围之外的数据会显示数据错误并要求重新输入为了体现不同排序法的复杂度差距 我们输入 30000 让程序随机生成 30000 组数据7 / 23 文档可自由编辑打印输入了正确

8、范围的数据 ，显示功能菜单。通过选择不同的序号实现不同排序法的交换次数与比较次数转换我们首先选择 5 输出随机数 每排 6 个数字。进行右对齐规范化输出 输出后 sleep4000ms 后继续输出功能菜单8 / 23 文档可自由编辑打印依次输入 1、2、3、4 得到四种排序法的排序结果每一次输出完数据后都会暂停 4s 后输出主菜单然后 输入序号 7 进行比较（序号选择顺序随意。进行比较前可以不先运行 1.2.3.4 因为各功能独立）9 / 23 文档可自由编辑打印程序会规范化输出四种排序法的比较次数交换次数与使用时间（ms） 。输出结果后会要求重新数据数量，进行随机数的重新生成输入 0。直接退

9、出程序。以下是以 49999 为随机数据数量与以 400 为随机数据数量直接进行的四种排序法的比较结果10 / 23 文档可自由编辑打印11 / 23 文档可自由编辑打印参考文献1Brian W.Kernighan/Dennis M.Ritchie C 程序设计经典M 机械工业出版社 20142杨丽 郭锐 陈雪峰 C 语言程序开发范例经典M 人民邮电出版社 20133Ivor Horton C 语言入门经典第五版M 清华大学出版社4戴艳 零基础学算法 机械工业出版社M 20145Mdash 数据结构与算法分析 C 语言描述M 机械工业出版社 20146Windows 各种计时函数总结 More

10、WindowsS12 / 23 文档可自由编辑打印附 录（程序清单）#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

11、 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_n

12、umber50000,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:13 / 23 文档可自由编辑打印while (1)printf(请输入数据生成数量(1number= 50000 | length = 1)printf(数据生成

13、范围错误！请重新输入n);elsebreak; random_number(basic_number, length);memcpy(select_number, basic_number, sizeof(basic_number);memcpy(bubble_number, basic_number, sizeof(basic_number);memcpy(quick_number, basic_number, sizeof(basic_number);memcpy(insert_number, basic_number, sizeof(basic_number); /拷贝随机数到四种排序法

14、所对应的数组中while (1)print2();printf(请输入序号:);scanf(%d,&choose);if (choose = 1|choose=7)select_time=select_sort(select_number, select_count, length);if (choose != 7)print_answer(select_count0, select_count1, select_time);memcpy(select_number, basic_number, sizeof(int)*length);/重置数组为未排序状态memset(select_

15、count, 0, sizeof(select_count);select_time = 0;/重置变量Sleep(4000);if (choose = 2|choose=7)bubble_time = bubble_sort(bubble_number, bubble_count, length);14 / 23 文档可自由编辑打印if (choose != 7)print_answer(bubble_count0, bubble_count1, bubble_time);memcpy(bubble_number, basic_number, sizeof(int)*length);/重置数

16、组为未排序状态memset(bubble_count, 0, sizeof(bubble_count);bubble_time = 0;/重置变量Sleep(4000);if (choose = 3|choose=7)QueryPerformanceFrequency(&nFreq);QueryPerformanceCounter(&nBeginTime);quick_sort(quick_number, quick_count, 1, length - 1);QueryPerformanceCounter(&nEndTime);quick_time = (double

17、)(nEndTime.QuadPart - nBeginTime.QuadPart) * 1000 / (double)nFreq.QuadPart;if (choose != 7)print_answer(quick_count0, quick_count1, quick_time);memcpy(quick_number, basic_number, sizeof(int)*length);/重置数组为未排序状态memset(quick_count, 0, sizeof(quick_count);quick_time = 0;/重置变量Sleep(4000);if (choose = 4|

18、choose=7)insert_time = insert_sort(insert_number, insert_count, length);if (choose != 7)print_answer(insert_count0, insert_count1, insert_time);memcpy(insert_number, basic_number, sizeof(int)*length);/重置数组为未排序状态memset(insert_count, 0, sizeof(insert_count);insert_time = 0;/重置变量15 / 23 文档可自由编辑打印Sleep(

19、4000);if (choose = 5)int temp = 0;for (int i = 0;i length;i+)printf(%7d,basic_numberi);temp+;if (temp % 6 = 0)printf(n);Sleep(4000);if (choose = 6)goto leap;if (choose = 7)printf( 选择排序法 冒泡排序法 快速排序法 插入排序法n);printf(比较次数 %-14d%-14d%-14d%-14dn,select_count0, bubble_count0,quick_count0,insert_count0);pri

20、ntf(交换次数 %-14d%-14d%-14d%-14dn,select_count1, bubble_count1, quick_count1, insert_count1);printf(使用时间(ms) %-14.4lf%-14.4lf%-14.4lf%-14.4lfn,select_time,bubble_time,quick_time,insert_time);Sleep(5000); goto leap;if (choose = 0)printf(谢谢使用n);return;if(choose7)printf(序号输入错误，请重新输入n);16 / 23 文档可自由编辑打印con

21、tinue;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)p

22、rintf(比较次数:%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 len;i+)17 / 23 文档可自由编辑打印ai = random(100000); /随机生成0-99999的数double select_sort(int a,int count, int len) /选择排序法int i, j, k, t;int compare=0; /比较次数统计int change=0;/交换次数统计do

23、uble time;QueryPerformanceFrequency(&nFreq);QueryPerformanceCounter(&nBeginTime);for (i = 0;ilen;i+)k = ai;t = i;for (j = i;jlen;j+)compare+;/此处进行了比较 if (ajk)k = aj;t = j;at = ai;/此处进行了交换ai = k;change+;QueryPerformanceCounter(&nEndTime);count0 = compare;count1 = change;return time = (dou

24、ble)(nEndTime.QuadPart - nBeginTime.QuadPart)*1000 / (double)nFreq.QuadPart;double bubble_sort(int a,int count, int n)/冒泡排序法18 / 23 文档可自由编辑打印int i, j, temp;int compare=0;/比较次数统计int change=0;/数据交换次数统计double time;QueryPerformanceFrequency(&nFreq);QueryPerformanceCounter(&nBeginTime);for (j = 0

25、; j n - 1 ; j+)for (i = 0; i ai + 1)temp = ai;ai = ai + 1;ai + 1 = temp;change+;/若条件成立进行交换;QueryPerformanceCounter(&nEndTime);count0 = compare;count1 = change;return time = (double)(nEndTime.QuadPart - nBeginTime.QuadPart)*1000 / (double)nFreq.QuadPart;void quick_sort(int a, int count, int left,

26、 int right)/快速排序法int i, j, t, temp;if (left right)return;/不能省略 否则无法停止。导致出现堆栈溢出情况i = left;j = right;temp = aleft;while (i != j)19 / 23 文档可自由编辑打印while (aj = temp&i j)j-;count0+;/进行一次比较进入循环 if (aj =t比较条件未满足跳出循环，while (ai = temp&i temp)count0+;if (i j)t = ai;ai = aj;aj = t;count1+;/满足条件进行一次交换ale

27、ft = ai;ai = temp; /基准点交换quick_sort(a, count, left, i - 1);quick_sort(a, count, i + 1, right);double insert_sort(int a, int count, int len)/直接插入排序法int compare = 0;int change = 0;double time;20 / 23 文档可自由编辑打印QueryPerformanceFrequency(&nFreq);QueryPerformanceCounter(&nBeginTime);for (int i = 1

28、; i = 0 & ak = t; k-)ak + 1 = ak;compare+;change+;ak + 1 = t;compare+;QueryPerformanceCounter(&nEndTime);count0 = compare;count1 = change;return time = (double)(nEndTime.QuadPart - nBeginTime.QuadPart)*1000 / (double)nFreq.QuadPart;/*以下为标准排版的源代码*/#include#include#include/生成随机数时所用随机数种子函数以及时间函

29、数#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, i

30、nt 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_c

31、ount2 = 0, bubble_count2 = 0 , quick_count2 = 0 , insert_count2 = 0 ;double select_time, bubble_time, quick_time, insert_time;print();leap:while (1)printf(请输入数据生成数量(1number= 50000 | length = 1)printf(数据生成范围错误！请重新输入n);elsebreak; random_number(basic_number, length);memcpy(select_number, basic_number,

32、sizeof(basic_number);memcpy(bubble_number, basic_number, sizeof(basic_number);memcpy(quick_number, basic_number, sizeof(basic_number);memcpy(insert_number, basic_number, sizeof(basic_number); /拷贝随机数到四种排序法所对应的数组中while (1)print2();printf(请输入序号:);scanf(%d,&choose);if (choose = 1|choose=7)select_tim

33、e=select_sort(select_number, select_count, length);if (choose != 7)print_answer(select_count0, select_count1, select_time);memcpy(select_number, basic_number, sizeof(int)*length);/重置数组为未排序状态memset(select_count, 0, sizeof(select_count);select_time = 0;/重置变量Sleep(4000);if (choose = 2|choose=7)bubble_t

34、ime = bubble_sort(bubble_number, bubble_count, length);if (choose != 7)print_answer(bubble_count0, bubble_count1, bubble_time);memcpy(bubble_number, basic_number, sizeof(int)*length);/重置数组为未排序状态memset(bubble_count, 0, sizeof(bubble_count);bubble_time = 0;/重置变量Sleep(4000);if (choose = 3|choose=7)Quer

35、yPerformanceFrequency(&nFreq);QueryPerformanceCounter(&nBeginTime);quick_sort(quick_number, quick_count, 1, length - 1);QueryPerformanceCounter(&nEndTime);quick_time = (double)(nEndTime.QuadPart - nBeginTime.QuadPart) * 1000 / (double)nFreq.QuadPart;if (choose != 7)print_answer(quick_cou

36、nt0, quick_count1, quick_time);memcpy(quick_number, basic_number, sizeof(int)*length);/重置数组为未排序状态memset(quick_count, 0, sizeof(quick_count);quick_time = 0;/重置变量Sleep(4000);if (choose = 4|choose=7)insert_time = insert_sort(insert_number, insert_count, length);if (choose != 7)print_answer(insert_count

37、0, insert_count1, insert_time);memcpy(insert_number, basic_number, sizeof(int)*length);/重置数组为未排序状态memset(insert_count, 0, sizeof(insert_count);insert_time = 0;/重置变量Sleep(4000);if (choose = 5)int temp = 0;for (int i = 0;i length;i+)printf(%7d,basic_numberi);temp+;if (temp % 6 = 0)printf(n);Sleep(4000

38、);if (choose = 6)goto leap;if (choose = 7)printf( 选择排序法 冒泡排序法 快速排序法 插入排序法n);printf(比较次数 %-14d%-14d%-14d%-14dn,select_count0, bubble_count0,quick_count0,insert_count0);printf(交换次数 %-14d%-14d%-14d%-14dn,select_count1, bubble_count1, quick_count1, insert_count1);printf(使用时间(ms) %-14.4lf%-14.4lf%-14.4lf

39、%-14.4lfn,select_time,bubble_time,quick_time,insert_time);Sleep(5000); goto leap;if (choose = 0)printf(谢谢使用n);return;if(choose7)printf(序号输入错误，请重新输入n);continue;void print()printf(n 排序方法比较程序的设计与实现n);printf( -143401010518 韩冰nnnn);void print2()printf(n请选择您要使用的排序方法n);printf( 1-选择排序法n);printf( 2-冒泡排序法n);p

40、rintf( 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 len;i+)ai = rand

41、om(100000); /随机生成0-99999的数double select_sort(int a,int count, int len) /选择排序法int i, j, k, t;int compare=0; /比较次数统计int change=0;/交换次数统计double time;QueryPerformanceFrequency(&nFreq);QueryPerformanceCounter(&nBeginTime);for (i = 0;ilen;i+)k = ai;t = i;for (j = i;jlen;j+)compare+;/此处进行了比较 if (aj

42、k)k = aj;t = j;at = ai;/此处进行了交换ai = k;change+;QueryPerformanceCounter(&nEndTime);count0 = compare;count1 = change;return time = (double)(nEndTime.QuadPart - nBeginTime.QuadPart)*1000 / (double)nFreq.QuadPart;double bubble_sort(int a,int count, int n)/冒泡排序法int i, j, temp;int compare=0;/比较次数统计int change=0;/数据交换次数统计double time;QueryPerformanceFrequency(&nFreq);QueryPerfor