综合排序-数据结构课程设计.pdf

《综合排序-数据结构课程设计.pdf》由会员分享，可在线阅读，更多相关《综合排序-数据结构课程设计.pdf（19页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、 1 题 目：综合排序-数据结构课程设计 院 系：信息工程学院 专 业：计算机科学与技术 班 级：姓 名：学 号：指导老师:时 间：2 目 录 一、问题描述.3 二、内容简介.3 2.1 基本要求：.3 2.2.算法思想：.3 2.3.模块划分：.5 2.4.数据结构：.6 2.5.源程序：.6 2.6.测试情况：.14 三、小结.18 3 一、问题描述 利用随机函数产生 N 个随机整数（20000 以上），对这些数进行多种方法进行排序。要求：1)至少采用三种方法实现上述问题求解（提示，可采用的方法有插入排序、希尔排序、起泡排序、快速排序、选择排序、堆排序、归并排序）。并把排序后的结果保存在不

2、同的文件中。2)统计每一种排序方法的性能（以上机运行程序所花费的时间为准进行对比），找出其中两种较快的方法。3)如果采用 4 种或 4 种以上的方法者，可适当加分。二、内容简介 2.1 基本要求：（1）设计一个的菜单将在实现的功能显示出来，并有选择提示（2）分别实现直接插入排序、折半插入排序、希尔排序、冒泡排序、快速排序、简单排序、堆排序算法；（3）通过多种测试数据，对各种排序算法的时间复杂度和空间复杂度进行比较 2.2.算法思想：1.处理流程图 4 开始 直接插入排序 时间效率比较 直接选择排序 显示菜单 冒泡排序 快速排序 堆 排序 显示随机数 显示排序后的的数据和时间效率 输入序号 结束

3、 退出显示各个排序法对同一组数据排序所用的时间和其中两种较快的方法 1 2 3 4 5 6 7 0 void BubleSort(double a)时间数组的冒泡排序 void InsertSort(int a,int p)void SelectSort(int a,int p)void Disp(int a)void creatheap(int a,int i,int n)void heapsort(int a,int n,int p)double TInsertSort(int a,int p)void quicksort(int a,int n,int p)void BubbleSort

4、(int a,int p)double TSelectSort(int a,int p)double Tquicksort(int a,int left,int right,int p)double TBubbleSort(int a,int p)double Theapsort(int a,int n,int p)5 3.设计一个高精度时间函数，分别测试各种排序的时间消耗；4.在主函数中，用开关语句 swtich()case 值 1;break;case 值n;break;Default 语句序列:n+1;调用各种排序算法，各种排序的时间消耗函数，从而在屏幕上输出供选择的菜单，各种排序时间和

5、空间复杂度的比较。2.3.模块划分：1.输入初始数据函数：int MakeList(RECNODE*r)2.输出未排序前的数据函数：void UndealoutList(RECNODE*r,int n)3.处理后的序列函数：void DealoutList(RECNODE*r,int n)4.这种排序的算法：void InsertSort(RECNODE*r,int n)/直接插入排序 void BiInsertionSort(RECNODE*r,int n)/折半插入排序 void BubleSort(RECNODE*r,int n)/冒泡排序 int Partition(RECNODE*r

6、,int*low,int*high)/一趟快速排序 void QuickSort(RECNODE*r,int start,int end)/快速排序 void SeleSort(RECNODE*r,int n)/直接选择排序 void ShellSort(RECNODE*r,int n)/希尔排序 void Sift(RECNODE*r,int i,int m)void HeapSort(RECNODE*r,int n)/堆排序 5.排序时间测试函数：double TInsertSort(int len,RECNODE*a,int p)6 2.4.数据结构：1.预定义常量和自定义类型：#def

7、ine MAXSIZE 100 typedef struct int key;RECNODE;2.基本函数的算法用以下形式表示：函数类型 函数名（函数参数表）/算法说明 语句序列/函数名。3.定义 int b,t,i,j;/b 为记录交换的次数，t 为记录排序的趟数,i 为排序的数据，j 为暂存数据的临时变量。4.输入初始数据函数中定义 int k,j，k 为输入数据个数，j 为输入的数据。5.快速排序中定义 static int w=0,int*low，*high。6.在直接选择排序中定义 int z，临时储存 i 的值。7.在希尔排序中定义 int dk，记录前后位置的增量。8.在排序时间

8、消耗测试的函数和主函数中定义了 int p，为菜单的序号。9.在主函数中定义 int len，为测试数据的总长度。2.5.源程序：插入排序核心代码 void InsertSort(int a,int p)int i,j,temp;7 for(i=1;i0&aj-1temp;j-)aj=aj-1;aj=temp;选择排序核心代码 void SelectSort(int a,int p)int i,j,k;for(i=0;iN-1;i+)k=i;for(j=i+1;jN;j+)if(ajak)k=j;if(k!=i)int temp;temp=ak;ak=ai;ai=temp;冒泡排序算法核心代码

9、 void BubbleSort(int a,int p)int i,j,temp;for(i=0;ii;j-)/*比较,找出本趟最小关键字的记录*/if(ajaj-1)temp=aj;/*进行交换,将最小关键字记录前移*/aj=aj-1;8 aj-1=temp;创建堆核心代码 void creatheap(int a,int i,int n)int j;int t;t=ai;j=2*(i+1)-1;while(j=n)if(jn)&(ajaj+1)j+;if(t=0;i-)creatheap(a,i,n-1);for(i=n-1;i=1;i-)t=a0;a0=ai;ai=t;creathea

10、p(a,0,i-1);9 快速排序核心代码 void quicksort(int a,int n,int p)int i,j,low,high,temp,top=-1;struct node int low,high;stN;top+;sttop.low=0;sttop.high=n-1;while(top-1)low=sttop.low;high=sttop.high;top-;i=low;j=high;if(lowhigh)temp=alow;while(i!=j)while(itemp)j-;if(ij)ai=aj;i+;while(ij&aitemp)i+;if(ij)aj=ai;j-

11、;ai=temp;top+;sttop.low=low;sttop.high=i-1;top+;sttop.low=i+1;sttop.high=high;时间部分代码 double TInsertSort(int a,int p)int i;int bN;for(i=0;iN;i+)bi=ai;LARGE_INTEGER m_liPerfFreq=0;QueryPerformanceFrequency(&m_liPerfFreq);LARGE_INTEGER m_liPerfStart=0;QueryPerformanceCounter(&m_liPerfStart);InsertSort(

12、b,p);LARGE_INTEGER liPerfNow=0;QueryPerformanceCounter(&liPerfNow);double time=liPerfNow.QuadPart-m_liPerfStart.QuadPart;10 time/=m_liPerfFreq.QuadPart;if(p!=6)Disp(b);getchar();printf(n 用直接插入排序法用的时间为%f 秒；,time);FILE*fp;fp=fopen(直接插入排序.txt,w);for(i=0;iN;i+)fprintf(fp,%d,bi);fclose(fp);return(time);d

13、ouble TSelectSort(int a,int p)int i;int bN;for(i=0;iN;i+)bi=ai;LARGE_INTEGER m_liPerfFreq=0;QueryPerformanceFrequency(&m_liPerfFreq);LARGE_INTEGER m_liPerfStart=0;QueryPerformanceCounter(&m_liPerfStart);SelectSort(b,p);if(p!=6)Disp(b);getchar();LARGE_INTEGER liPerfNow=0;QueryPerformanceCounter(&liPe

14、rfNow);double time=liPerfNow.QuadPart-m_liPerfStart.QuadPart;time/=m_liPerfFreq.QuadPart;printf(n 用直接选择排序法用的时间为%f 秒；,time);FILE*fp;fp=fopen(直接选择排序.txt,w);for(i=0;iN;i+)fprintf(fp,%d,bi);fclose(fp);return(time);double TBubbleSort(int a,int p)int i;int bN;for(i=0;iN;i+)bi=ai;11 LARGE_INTEGER m_liPerfF

15、req=0;QueryPerformanceFrequency(&m_liPerfFreq);LARGE_INTEGER m_liPerfStart=0;QueryPerformanceCounter(&m_liPerfStart);BubbleSort(b,p);LARGE_INTEGER liPerfNow=0;QueryPerformanceCounter(&liPerfNow);double time=liPerfNow.QuadPart-m_liPerfStart.QuadPart;time/=m_liPerfFreq.QuadPart;if(p!=6)Disp(b);getchar

16、();printf(n 用冒泡排序法用的时间为%f 秒；,time);FILE*fp;fp=fopen(冒泡排序.txt,w);for(i=0;iN;i+)fprintf(fp,%d,bi);fclose(fp);return(time);double Theapsort(int a,int n,int p)int i;int bN;for(i=0;iN;i+)bi=ai;LARGE_INTEGER m_liPerfFreq=0;QueryPerformanceFrequency(&m_liPerfFreq);LARGE_INTEGER m_liPerfStart=0;QueryPerform

17、anceCounter(&m_liPerfStart);heapsort(b,N,p);LARGE_INTEGER liPerfNow=0;QueryPerformanceCounter(&liPerfNow);double time=liPerfNow.QuadPart-m_liPerfStart.QuadPart;time/=m_liPerfFreq.QuadPart;if(p!=6)Disp(b);getchar();printf(n 用堆排序法用的时间为%f 秒；,time);FILE*fp;fp=fopen(堆排序.txt,w);for(i=0;iN;i+)fprintf(fp,%d

18、,bi);fclose(fp);return(time);12 double Tquicksort(int a,int n,int p)int i;int bN;for(i=0;iN;i+)bi=ai;LARGE_INTEGER m_liPerfFreq=0;QueryPerformanceFrequency(&m_liPerfFreq);LARGE_INTEGER m_liPerfStart=0;QueryPerformanceCounter(&m_liPerfStart);quicksort(b,N,p);LARGE_INTEGER liPerfNow=0;QueryPerformance

19、Counter(&liPerfNow);double time=liPerfNow.QuadPart-m_liPerfStart.QuadPart;time/=m_liPerfFreq.QuadPart;if(p!=6)Disp(b);getchar();printf(n 用快速排序法用的时间为%f 秒；,time);FILE*fp;fp=fopen(快速排序.txt,w);for(i=0;iN;i+)fprintf(fp,%d,bi);fclose(fp);return(time);时间数组的冒泡排序 void BubleSort(double a)int i,j;double temp;f

20、or(i=1;i=i;j-)if(aj+1请在上述序号中选择一个并输入:);主函数代码 void main()int i,p,aN;srand(int)time(NULL);/*随机种子*/for(i=0;i谢谢使用!n);getchar();break;double TIMES5,TIMES15;/时间数组 switch(p)case 1:TInsertSort(a,p);printf(n 请按任意键继续.);getchar();break;case 2:TSelectSort(a,p);printf(n 请按任意键继续.);getchar();break;case 3:TBubbleSor

21、t(a,p);printf(n 请按任意键继续.);getchar();break;case 4:Tquicksort(a,N,p);printf(n 请按任意键继续.);getchar();break;case 5:Theapsort(a,N,p);printf(n 请按任意键继续.);getchar();break;case 6:system(cls);TIMES11=TIMES1=TInsertSort(a,p);TIMES12=TIMES2=TSelectSort(a,p);TIMES13=TIMES3=TBubbleSort(a,p);TIMES14=TIMES4=Tquicksor

22、t(a,N,p);TIMES15=TIMES5=Theapsort(a,N,p);getchar();BubleSort(TIMES);printf(nn);printf(排序这组数据两种较快的排序法分别是：n);if(TIMES1=TIMES11)printf(直接插入排序:%f 秒!n,TIMES1);if(TIMES1=TIMES12)printf(直接选择排序:%f 秒!n,TIMES1);if(TIMES1=TIMES13)printf(冒泡排序:%f 秒!n,TIMES1);if(TIMES1=TIMES14)printf(快速排序:%f 秒!n,TIMES1);if(TIMES1

23、=TIMES15)printf(堆排序:%f 秒!n,TIMES1);if(TIMES1!=TIMES2)if(TIMES2=TIMES11)printf(直接插入排序:%f 秒!n,TIMES2);if(TIMES2=TIMES12)printf(直接选择排序%f 秒!n,TIMES2);if(TIMES2=TIMES13)printf(冒泡排序%f 秒!n,TIMES2);if(TIMES2=TIMES14)printf(快速排序%f 秒!n,TIMES2);if(TIMES2=TIMES15)printf(堆排序%f 秒!n,TIMES2);printf(n 请按任意键继续.);sran

24、d(int)time(NULL);for(i=0;iN;i+)ai=rand()%30000+1;getchar();break;case 7:Disp(a);FILE*fp;fp=fopen(随机数.txt,w);for(i=0;iN;i+)fprintf(fp,%d,ai);fclose(fp);getchar();printf(n请 按 任 意 键 继续.);getchar();break;default:Wrong();printf(n 请按任意键继续.);getchar();break;15 2.6.测试情况：菜单界面 16 直接插入排序直接选择排序冒泡排序 17 快速排序堆排序时间

25、比较 18 显示随机数 三、小结 经过这次课程设计的锻炼，使我更加理解数据结构这门课程。在设计综合排序算法时，我不仅懂得了许多算法设计思想，而且更加了解了循环的使用。在课程设计中也遇到不少困难，如怎么编写冒泡排序算法，如何设计一个高精度时间算法函数。但是通过查阅资料，询问同学，在应用课本的前提下，拓展课外知识，完成了此次课程设计，虽然还有许多不足之处，如计算的时间精确度不太高，算法有点复杂，不够简洁，但是从中我学到了许多东西。我们不能拘泥于所学知识，应对其灵活运用。如并不是把书上的所有的排序算法照搬到课设中就可以了，还应自行定义数据类型和函数，不断的改进算法，达到正确性、可读性、健壮性的目的。在本次课设中要感谢谢小林老师细心指导和严格要求，还要感谢帮助过我的同学们，没有你们的帮助，也许现在我还没有得到结 19 果。谢谢大家!