《2022年数据结构c语言设计,比较各种排序方法的效率 .pdf》由会员分享，可在线阅读，更多相关《2022年数据结构c语言设计,比较各种排序方法的效率 .pdf（31页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、课程设计说明书设计名称：程序设计语言强化课程设计题目：比较各种排序方法的效率学生姓名：梁汉荣专业：网络工程班级： 10网络工程 2 学号： 2010394236 指导教师：顾艳春日期： 2012 年 3 月 8 日名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 31 页 - - - - - - - - - 课程设计任务书一、设计题目比较各种排序方法的效率二、主要内容选择四种以上的排序方法，采用随机生成的数据，登记并比较各个排序方法的比较次数和交换次数，验证各个排序方法效率
2、的理论分析的结果。三、具体要求围绕课程设计的目的和意义，基本要求如下：每次随机生成的数据不小于100个采用顺序存储结构，登记多次结果经过大量的统计计算，给出各种排序方法的平均效率的比较。把统计结果与理论分析结论进行对照。四、进度安排名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 31 页 - - - - - - - - - 1、资料查找、系统分析，概要设计；时间安排2 天2、系统详细设计、功能设计；时间安排2 天3、算法实现、编程调试；时间安排5-7 天4、资料整理、课程
3、设计说明书编写。时间安排1 天五、完成后应上交的材料1、课程设计说明书（所使用的数据结构说明、程序流程图、功能模块图、核心算法等）2、相关源程序文件六、总评成绩指导教师签名日期年月日系 主 任审核日期年月日目录名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 31 页 - - - - - - - - - 一、设计任务的主要算法分析,1 1.1 主要算法具体分析,2 二、程序的流程图 ,3 各种 排 序 算法 的 N- S 图,3 1. 总流程图模块 , 3 2. 直接插入排
4、序模块 ,4 3. 冒泡排序模块,5 4. 简单选择模块 ,5 5. 快 速 排 序 模 块,6 6. 堆 排 序 模 块,6 三、各个模块的源代码,7 3 1 各种排序算法 ,7 1. 直接插入排序函数 ,7 2. 冒泡排序函数 , 8 3.简单选择排序函数 ,9 4. 快速排序函数 , 10 5. 堆排序函数 , 11 6. 输出函数 , 13 7. 随机生成函数 , 13 8. 主函数, 16 四、程序运行效果图,20 4.1登陆画面,20 4.2 各种排序结果显示画面（100 个数据随机生成5 次）, 21 4.3 总的、平均的比较次数和交换次数显示画面（100 个数据随机名师资料总结
5、 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 31 页 - - - - - - - - - 生成 5 次）,23 4.4 总的、平均的比较次数和交换次数显示画面（1000 个数据随机生成100 次）,24 五、使用说明 ,24六、设计心得,24 6.1 课程设计中遇到的主要问题和解决方法,24 6.2 本程序的创新和得意之处,25 6.3 设计中存在的不足及改进的设想,25 6.4 本次课程设计的感想和心得体会,25 名师资料总结 - - -精品资料欢迎下载 - - - - - -
6、 - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 31 页 - - - - - - - - - 佛山科学技术学院课程设计用纸1 一. 算法分析直接插入排序：将记录插入到已排好序的有序表中，得到一个新的，记录数增加的有序表。冒泡排序：是基于交换排序的一种算法。它是依次两两比较待排序元素；若为逆序（递增或递减）则进行交换，将待排序元素从左至右比较一遍称为一趟“ 冒泡” 。 每趟冒泡都将待排序列中的最大（小）关键字交换到最后位置，直到全部元素有序为止。简单选择排序：令i 从 1 至 n-1，进行 n-1 趟选择操作。快速排序：通过一趟排序将待
7、排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，已达到整个序列有序。堆排序：使记录序列按关键字非递减有序排列，则在堆排序的算法中先建一个“大顶堆”，即先选得一个关键字为最大的记录并与序列中最后一个记录交换，然后对序列中前n-1 记录进行筛选，重新将它调整为一个 “大顶堆”，如此反复直至排序结束。随机生成函数： 用 srand(unsigned)time(NULL)随机生成数据并使用主程序直接插入冒泡排序简单选择快速排序堆排序随机生成名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - -
8、 - - - 名师精心整理 - - - - - - - 第 6 页，共 31 页 - - - - - - - - - 佛山科学技术学院课程设计用纸2 不同排序方法排序。定义结构体数组typedef int keytype; /定义关键字类型为整型typedef struct keytype key; datatype; /记录类型datatype RMAXSIZE; / 定义结构体数组1.1 主要算法具体分析：这个排序算法设计个以静态结构体应用为基础加上C 的基础语法一起的一个综合系统程序。1 主程序是 goto 语句和 for 循环的应用2 直接插入函数是一个将记录插入到已排好序的静态数组的
9、应用3 冒泡排序函数是一个将数据不断交换排序的应用4 简单选择函数是一个从n-i+1 个记录中选出最小关键字并和第i 个记录交换的应用5 快速排序函数是一个将每趟记录分成独立两部分并比较交换的应用6 堆排序函数是一个将记录建成堆并交换的排序的应用7 随机生成函数是用srand(unsigned)time(NULL)随机生成数据的应用8 输出函数是一个对排好序的组数输出的应用名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 7 页，共 31 页 - - - - - - - - - 佛山科
10、学技术学院课程设计用纸3 二程序的流程图2.1 总流程图说明：利用判断语句判断，若n100则执行 goto 语句；利用 for 循环语句执行随机生成函数并输出结果。输入随机生成数据的个数n100 T F goto m; 输入随机生成的次数for(i=0;it;i+) rand_select(n); 统计第 %d 次随机数据的比较次数和交换次数平均比较次数和平均移动次数名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 8 页，共 31 页 - - - - - - - - - 佛山科学技术
11、学院课程设计用纸4 2. 2 直接插入排序函数说明：利用外循环for 语句，内嵌判断语句if(Ri.keyRi-1.key) 和内循环 for 语句。for(i=2;i=n;+i) a0+ T if(Ri.keyRi-1.key) F R0=Ri;Ri=Ri-1; b0+=2; for(j=i-2;R0.keyRj+1.key) 进行排序。2.4 简单选择函数for(i=1;in;i+) for(j=i+1;j=n;j+) T if(Rj.keyRk.key) F a2+; RkRi ;b2+=3; k=i; k=j; if(i!=k) T F for(i=1;i=n-1;i+) for(j=
12、1;jRj+1.key) F a1+; Rj Rj+1 b1+=3; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 10 页，共 31 页 - - - - - - - - - 佛山科学技术学院课程设计用纸6 说明： for 外循环，内嵌 for 循环和判断语句来进行选择交换排序。2.5 快速排序函数说明： 判断 if(low0;-i) for(i=n;i1;-i) R1Ri b4+=3; HeapAdjust(R,i,n); HeapAdjust(R,1,i-1); int i；T
13、 if(lowhigh) F int i; i=Partition(R,low,high); 递归调用 QSort(R,low,i-1); 递归调用 QSort(R,i+1,high); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 11 页，共 31 页 - - - - - - - - - 佛山科学技术学院课程设计用纸7 三原代码程序3.1 各种排序算法#include #include #include #include #define MAXSIZE 50000 typede
14、f int keytype; /定义关键字类型为整型typedef struct keytype key; datatype; /记录类型datatype RMAXSIZE; /定义结构体数组int a5=0,b5=0; /分别定义比较次数和交换次数double c5,Ttime; /直接插入排序void Insert_Sort(datatype R,int n)/直接插入排序 int i,j; for(i=2;i=n;+i) a0+; if(Ri.keyRi-1.key) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精
15、心整理 - - - - - - - 第 12 页，共 31 页 - - - - - - - - - 佛山科学技术学院课程设计用纸8 R0=Ri; /复制为哨兵Ri=Ri-1; b0+=2; for(j=i-2;R0.keyRj.key;-j) Rj+1=Rj; /记录后移 b0+; a0+; if(j!=0) a0+; Rj+1=R0; /插入到正确位置b0+; /冒泡排序void Bubble_Sort(datatype R,int n)/冒泡排序 int i,j; for(i=1;i=n-1;i+) for(j=1;jRj+1.key) R0=Rj; Rj=Rj+1; /将 Rj 与 Rj
16、+1 交换Rj+1=R0; b1+=3; /简单选择排序void Select_Sort(datatype R,int n)/简单选择排序 int i,j,k; for(i=1;in;i+) k=i; for(j=i+1;j=n;j+) a2+; if(Rj.keyRk.key) /选择第 i 小的记录k=j; if(i!=k) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 14 页，共 31 页 - - - - - - - - - 佛山科学技术学院课程设计用纸10 R0=Rk;
17、Rk=Ri; /将 Rk 与 Ri 交换Ri=R0; b2+=3; /快速排序int Partition(datatype R,int low,int high) int pivotkey; R0=Rlow; b3+; pivotkey=Rlow.key; /枢轴记录关键字while(lowhigh) while(low=pivotkey) a3+; -high; if(lowhigh) Rlow=Rhigh; /将比枢轴记录小的记录移到低端a3+;b3+; while(lowhigh&Rlow.keyR0.key) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - -
18、 - - - - - - - - - 名师精心整理 - - - - - - - 第 15 页，共 31 页 - - - - - - - - - 佛山科学技术学院课程设计用纸11 a3+; +low; if(lowhigh) Rhigh=Rlow; /将比枢轴记录大的记录移到高端a3+;b3+; Rlow=R0;b3+; return low; /返回枢轴位置/Partition void QSort(datatype R,int low,int high)/快速排序 int i; if(lowhigh) i=Partition(R,low,high); /将 Rlow.high一分为二QSor
19、t(R,low,i-1); /对低子表递归排序， i 是枢轴位置QSort(R,i+1,high); /对高子表递归排序 /QSort /堆排序void HeapAdjust(datatype R,int s,int m) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 16 页，共 31 页 - - - - - - - - - 佛山科学技术学院课程设计用纸12 datatype rc;int j; rc=Rs; for(j=2*s;j=m;j*=2) /沿 key 较大的孩子节点向
20、下筛选 if(jm & Rj.keyRj+1.key) a4+;+j; /j为 key 较大记录的下标if(jRj.key) break; Rs=Rj; b4+; s=j; Rs=rc; /插入/HeapAdjust void HeapSort(datatype R,int n)/堆排序 int i; for(i=n/2;i0;-i) HeapAdjust(R,i,n); /将 R1.n建成大顶堆for(i=n;i1;-i) R0=R1; R1=Ri; /将 R1 与 Ri 交换名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名
21、师精心整理 - - - - - - - 第 17 页，共 31 页 - - - - - - - - - 佛山科学技术学院课程设计用纸13 Ri=R0; b4+=3; HeapAdjust(R,1,i-1); /将 R1.i-1重新调整为大顶堆 /HeapSort /输出函数void Pri(datatype R,int n)/输出函数 int i; for(i=1;i=n;i+) printf(%d ,Ri.key); printf(n); /随机生成函数void rand_select(int n)/随机生成函数 int i; LARGE_INTEGER m_liPerfFreq=0;LAR
22、GE_INTEGER m_liPerfStart=0; LARGE_INTEGER liPerfNow=0; datatype R1MAXSIZE, R2MAXSIZE,R3MAXSIZE,R4MAXSIZE; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 18 页，共 31 页 - - - - - - - - - 佛山科学技术学院课程设计用纸14 for (i=1; i=n; i+) printf(%d , Ri.key=rand()%n); printf(n); for(i=1
23、;i=n;i+) R1i.key=Ri.key; for(i=1;i=n;i+) R2i.key=Ri.key; for(i=1;i=n;i+) R3i.key=Ri.key; for(i=1;i=n;i+) R4i.key=Ri.key; QueryPerformanceFrequency(&m_liPerfFreq); QueryPerformanceCounter(&m_liPerfStart); /计时开始Insert_Sort(R, n); /直接插入排序QueryPerformanceCounter(&liPerfNow); /计时结束 Ttime=(liPerfNow.QuadP
24、art)-(m_liPerfStart.QuadPart) *1000.0/m_liPerfFreq.QuadPart; c0+=Ttime; printf(插入排序后数据的顺序 :n); Pri(R,n); QueryPerformanceFrequency(&m_liPerfFreq); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 19 页，共 31 页 - - - - - - - - - 佛山科学技术学院课程设计用纸15 QueryPerformanceCounter(&m
25、_liPerfStart); /计时开始Bubble_Sort(R1, n); /冒泡排序QueryPerformanceCounter(&liPerfNow); /计时结束 Ttime=(liPerfNow.QuadPart)-(m_liPerfStart.QuadPart) *1000.0/m_liPerfFreq.QuadPart; c1+=Ttime; printf(冒泡排序后数据的顺序 :n); Pri(R1,n); QueryPerformanceFrequency(&m_liPerfFreq); QueryPerformanceCounter(&m_liPerfStart); /
26、计时开始Select_Sort(R2, n); /简单选择排序QueryPerformanceCounter(&liPerfNow); /计时结束 Ttime=(liPerfNow.QuadPart)-(m_liPerfStart.QuadPart) *1000.0/m_liPerfFreq.QuadPart; c2+=Ttime; printf(简单排序数据的顺序 :n); Pri(R2,n); QueryPerformanceFrequency(&m_liPerfFreq); QueryPerformanceCounter(&m_liPerfStart); /计时开始QSort(R3,1,
27、n); /快速排序QueryPerformanceCounter(&liPerfNow); /计时结束 Ttime=(liPerfNow.QuadPart)-(m_liPerfStart.QuadPart) *1000.0/m_liPerfFreq.QuadPart; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 20 页，共 31 页 - - - - - - - - - 佛山科学技术学院课程设计用纸16 c3+=Ttime; printf(快速排序后数据的顺序 :n); Pri(
28、R3,n); QueryPerformanceFrequency(&m_liPerfFreq); QueryPerformanceCounter(&m_liPerfStart); /计时开始HeapSort(R4,n); /堆排序QueryPerformanceCounter(&liPerfNow); /计时结束 Ttime=(liPerfNow.QuadPart)-(m_liPerfStart.QuadPart) *1000.0/m_liPerfFreq.QuadPart; c4+=Ttime; printf(堆排序后数据的顺序 :n); Pri(R4,n); /主函数void main()
29、 int i,n,t; srand(unsigned)time(NULL);/使用系统定时 / 计数器的值 /做为随机种子每次运行， 显示的随机数会是伪随机数, 结果都不同名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 21 页，共 31 页 - - - - - - - - - 佛山科学技术学院课程设计用纸17 printf(n); printf(n); printf(n); printf( *-*n); m:printf( |请输入随机生成数据的个数|n); printf( *-*
30、n); scanf(%d,&n); if(n100) printf(取数个数不能小于 100, 请重新输入 !n); goto m; printf(n); printf(n); printf( *-*n); printf( |请输入随机生成的次数 |n); printf( *-*n); scanf(%d,&t); printf(n); for(i=0;it;i+) printf(电脑第 %d次随机生成数据为 :n,i+1); rand_select(n); printf(统计 第%d 次随机 数据的 比较次 数和交 换次数为n,i+1); 名师资料总结 - - -精品资料欢迎下载 - - -
31、- - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 22 页，共 31 页 - - - - - - - - - 佛山科学技术学院课程设计用纸18 printf(*-*n); printf(*排 序方 式比 较 次 数交 换 次 数耗时n); printf(n); printf(*直接 %-10dt%-10dt%-12fn,a0,b0,c0); printf(n); printf(*冒泡 %-10dt%-10dt%-12fn,a1,b1,c1); printf(n); printf(*简单选择 %-10dt%-10dt%-12fn,a2,b2
32、,c2); printf(n); printf(*快速排序 %-10dt%-10dt%-12fn,a3,b3,c3); printf(n); printf(*堆排序 %-10dt%-10dt%-12fn,a4,b4,c4); printf(*-*n); printf(n); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 23 页，共 31 页 - - - - - - - - - 佛山科学技术学院课程设计用纸19 printf(求得平均比较次数和平均移动次数为 n); printf(
33、*-*n); printf(*排 序 方 式平 均比 较次 数平均 交 换 次 数平均耗时 n); printf(n); printf(*直接 %-10dt%-10dt%-12fn,a0/t,b0/t,c0/t); printf(n); printf(*冒泡 %-10dt%-10dt%-12fn,a1/t,b1/t,c1/t); printf(n); printf(*简单选择 %-10dt%-10dt%-12fn,a2/t,b2/t,c2/t); printf(n); printf(*快速排序 %-10dt%-10dt%-12fn,a3/t,b3/t,c3/t); printf(n); pri
34、ntf(*堆排序 %-10dt%-10dt%-12fn,a4/t,b4/t,c4/t); printf(*-*n); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 24 页，共 31 页 - - - - - - - - - 佛山科学技术学院课程设计用纸20 4 程序运行效果4.1 登陆界面 （100 个数据随机生成 5 次）名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第
35、25 页，共 31 页 - - - - - - - - - 佛山科学技术学院课程设计用纸21 4.2 各种排序结果显示画面 （100 个数据随机生成 5 次）第 1 次生成画面：名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 26 页，共 31 页 - - - - - - - - - 佛山科学技术学院课程设计用纸22 （100 个数据随机生成 5 次）第 5 次生成画面：名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - -
36、名师精心整理 - - - - - - - 第 27 页，共 31 页 - - - - - - - - - 佛山科学技术学院课程设计用纸23 4.3 总的和平均的比较次数和交换次数显示（100 个数据随机生成 5 次）名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 28 页，共 31 页 - - - - - - - - - 佛山科学技术学院课程设计用纸24 4.4 总的和平均的比较次数和交换次数显示（1000 个数据随机生成 100 次）五使用说明本设计比较各种排序算法的效率能在家用或
37、公用计算机上的VC软件上使用. 六设计心得（1）课程设计中遇到的主要问题和解决方法：上学期刚学完数据结构这本书， 毕竟都很少实践操作， 做这个比较名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 29 页，共 31 页 - - - - - - - - - 佛山科学技术学院课程设计用纸25 排序算法的效率都有些挑战，在这个课程设计中，主要是对于一些基本的知识，熟悉程度不够，特别是对于比较次数和交换次数的统计，刚开始是跟理论值相差甚大，然后自己看了好几遍的书和上网看了一些例题，根据输入两个
38、随机生成数据，比较次数为1 的依据才把问题解决。在编译时有时会出现较多的出错提示，这时要理解提示信息的含义，并据此改正错误。当编译提示的出错信息不止一条时，只须先注重其中第一条，每次改完一个错误后先编译一次，因为从第二个错误开始的若干错误很可能是随带错误，只要更正了第一个错误可能就没有错误出现了，而且我们可以用printf语句来测试某条有返回值的语句是否执行。（2）我的创新和得意之处：这 个 比 较 排 序 算 法 的 效 率 ， 使 用 系 统 定 时 / 计 数 器 的 值srand(unsigned)time(NULL) ;做为随机种子每次运行， 显示的随机数会是伪随机数 ,结果都不同，
39、是可以随意输入随机生成数据的个数，程序执行时可以输入大量数据，有利于精确求取比较次数和交换次数。（3）设计中存在的不足及改进的设想：设计过程中，程序不够简练，另外计时语句显得比较冗长，因为是高精度时间，因此统计比较次数和交换次数的工作应该是短期内能完成的工作，时间太长，误差会特别大，因为线程有占用时间片的因素存在。不过总的来说这个设计功能还是比较完善，它很好记录了排序过程中的时间差。（4）本次课程设计的感想和心得体会：此次课程设计，自拿到题目到完成整个编程，从理论到实践，在短短的天数，发现很多以前没有注意到的知识点，学到很多东西，巩名师资料总结 - - -精品资料欢迎下载 - - - - -
40、- - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 30 页，共 31 页 - - - - - - - - - 佛山科学技术学院课程设计用纸26 固了以前所学过的知识。通过这次课程设计使我懂得了理论与实际相结合是很重要的，只有理论知识是远远不够的，只有把所学的理论知识与实践相结合起来，才能提高自己的实际动手能力和独立思考的能力。在设计的过程中遇到问题，很多问题自己都可以解决，有时利用printf语句来测试某条语句是否执行，或用/* */暂且分隔出某部分来执行其他语句，能够很快的找到问题所在。在设计的过程中发现了自己的不足之处，对一些前面学过的知识理解得不够深刻，掌握得不够牢固，通过这次课程设计之后，我加深所学过的知识的理解与运用。在学习的过程中，独立完成，很好的提升了自己的能力，也锻炼了自己的耐力。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 31 页，共 31 页 - - - - - - - - -