湖州师范学院数据结构DS大作业

1、 求真学院数据结构课程设计大作业班 题 目：排序效率的比较专 业：计算机科学与技术学生姓名：学 号指导教师邵 斌完成日期：湖州师院求真学院信息工程系目 录一、实验内容概述1二、实验目的概述1三、解题思路的描述1四、源程序清单1五、程序调试及测试结果8六、结论9七、参考文献10【内容摘要】【关键字】XXXX，XXXXX，XXXXX，XXXXX(3到5个)数据结构是计算机存储、组织数据的方式。数据结构是指相互之间存在一种或多种特定关系的数据元素和集合。通常情况下，精心选择的数据结构可以带来更高的运行或者存储效率，处理各种问题。 该程序是用C语言编写的，它充分体现数据结构的理念与算法的魅力。 该程序

2、植入多种排序方法，这些排序方法的算法各具有特色，利用多种算法达到同一效果，正所谓“条条大路通罗马”。并且，该程序还收集各算法的运行时间，通过对耗时的比较，为用户挑选出两种最优化的排序方法。 关键字：排序 逻辑运算 数据结构 时间复杂度【Abstract】【Key words】XXXXX，XXXXX，XXXXX，XXXXXData structure is the way of computer storage and organization data. A data structure is a data element and a set of data elements that hav

3、e one or more specific relationships between each other. Typically, carefully selected data structures can be brought to a higher running or storage efficiency, processing a variety of problems. 该程序是用C语言编写的，它充分体现数据结构的理念与算法的魅力。 该程序植入多种排序方法，这些排序方法的算法各具有特色，利用多种算法达到同一效果，正所谓“条条大路通罗马”。并且，该程序还收集各算法的运行时间，通过

4、对耗时的比较，为用户挑选出两种最优化的排序方法。The program is written in C language, it fully reflects the concept of data structure and algorithm charm. The program is implanted in a variety of sorting methods, these sorting algorithms have the characteristics of each algorithm, the use of a variety of algorithms to achi

5、eve the same effect, is the so-called all roads lead to Rome. And, the program also collects the running time of each algorithm, through the time of the comparison, for the user to pick out two kinds of optimization of the sorting method. 关键字：排序 逻辑运算 数据结构 时间复杂度Keywords: sorting logic operation data

6、structure time complexity 一、 实验内容概述对于直接插入排序、选择排序、冒泡排序、Shell排序、快速排序和堆排序等几种常见的排序算法进行练习，并且比较各算法在不同长度数据下的优劣。 要求：（）被排序的对象由计算机随机生成，长度分别取，三种。 （）程序中要有对各种排序算法的比较，具体为比较次数和移动次数的统计。 （）对课设的结果做比较分析二、 实验目的概述 1. 巩固和加深学生对数据结构算法的理解，提高综合运用所学课程知识的能力； 2. 通过各个排序算法的实现，练习包括文件的读写、动态内存的申请、函数的应用、指针的应用等多种最基本的C语言操作； 3. 锻炼学生的动手能

7、力与培养其独立思考的能力。三、 解题思路的描述这是一个算法性能评价的程序，重点在于算法的性能评价上。实现排序功能可以有多种方法，判断一个算法性能好坏的标准主要有时间复杂度和空间复杂度。在当今系统资源相对充足的计算机系统中，时间复杂度便成为最主要的评价标准。 对于每一个排序算法，都应当有两个返回值：比较次数和移动次数。这里采用指针传递地址的方式，通过修改形参的地址从而可以改变实参的值。每个排序算法中除了含被排序对象指针外，还有两个整型变量指针，用于传递算法执行过程中的比较次数和移动次数。 取定一种排序对象的长度，由计算机产生一定量的伪随机数后，主函数调用各个排序子函数，但由于排序对象也是指向一维

8、数组的指针，在调用一次一种排序算法后，通过形参对指针的改变，被排序对象已经是有序的了。当再次调用其他函数时有可能使比较和移动次数达到最大或最小，就失去了比较的意义。因此，本程序中采用了子函数另开辟空间，参数只起到一个复制值的作用，在每个子函数结束前用delete() 来释放申请排序对象的指针，避免程序出现内存耗尽的情况。四、 源程序清单主要包括：#include#include#includeint a501,b501;int len;/数组长度 void number()srand(time(0);/srand函数是初始化随机数的种子 int i,t;printf(随机数长度：n);prin

9、tf(1. 长度为20n);printf(2. 长度为100n);printf(3. 长度为500n);printf(输入序号选择长度:);scanf(%d,&t);switch(t)case 1: n=20;for(i=1;i=n;i+)ai=rand()%1000+1; /1-1000的随机数 break;case 2: n=100;for(i=1;i=len;i+)ai=rand()%1000+1;break;case 3:n=500;for(i=1;i=len;i+)ai=rand()%1000+1;break;for(i=1;i=len;i+)bi=ai;printf(随机生成的%d

10、个数如下：n,len);for(i=1;i=len;i+)printf(%d ,ai);printf(n);typedefstructintkey;/关键字RecordNode;/排序结点类型typedefstructRecordNode*record;intn;/排序对象的大小ElemType;/排序对象的类型直接排序voidInsertSort(ElemTypeA,intn)inti,j;ElemTypex;for(i=1;i=0;j-)/从第i-1个开始往前找插入点if(x.stnAj.stn)Aj+1=Aj;elsebreak;Aj+1=x;/插入for(i=1;i=n;i+)prin

11、tf(%d ,ai); printf(n);printf(n);printf(比较次数：%d次n,i);printf(移动次数：%d次n,j);直接选择排序voidSelectSort(ElemTypeA,intn)inti,j,k;ElemTypex;for(i=0;i=n-2;i+)/每一趟选择最小元素并与Ai交换k=i;for(j=i+1;j=n-1;j+)/查找最小元素的下标if(Aj.stnAk.stn)k=j;if(k!=i)/交换x=Ai;Ai=Ak;Ak=x;for(i=1;i=n;i+)printf(%d ,ai); printf(n);printf(n);printf(比较

12、次数：%d次n,i);printf(移动次数：%d次n,j);冒泡排序voidBubbleSort(ElemTypeA,intn)inti,j,flag;/flag为交换标记ElemTypex;for(i=1;i=i;j-)/第i趟if(Aj.stnAj-1.stn)flag=1;/出现交换x=Aj;Aj=Aj-1;Aj-1=x;if(flag=0)return;for(i=1;i=n;i+)printf(%d ,ai); printf(n);printf(n);printf(比较次数：%d次n,i);printf(移动次数：%d次n,j);Shell排序void ShellSort(Elem

13、TypeA, intn,intdk) inti,j,temp;ElemTypex;for(i=dk;i=i%dk)&arrayjtemp;j-=dk)/比较与记录后移同时进行Aj+dk= Aj;if(j!=i-dk)Aj+dk=temp;/插入for(i=1;i=n;i+)printf(%d ,ai); printf(n);printf(n);printf(比较次数：%d次n,i);printf(移动次数：%d次n,j);快速排序voidQuickSort(ElemTypeA,ints,intt)/递归算法，对区间AsAt进行快速排序inti=s+1,j=t;ElemTypetemp,x=As

14、;/第一个为基准元素while(i=j)while(i=j&Ai.stn=x.stn)i+;/从左到右while(i=x.stn)j-;/从右到左if(ij)temp=Ai;Ai=Aj;Aj=temp;i+;j-;for(i=1;i=n;i+)printf(%d ,ai); printf(n);printf(n);printf(比较次数：%d次n,i);printf(移动次数：%d次n,j);if(s!=j)/交换基准元素As=Aj;Aj=x;if(sj-1)QuickSort(A,s,j-1);/处理左区间if(j+1=0;i-)Sift(A,n,i);/调整Ai.n-1使之为一个堆void

15、Sift(ElemTypeA,intn,inti)/调整Ai.n-1成为一个堆（它的左右子树已是一个堆）ElemTypex=Ai;intj=2*i+1;/j为i的左孩子while(j=n-1)/i有左子树if(j+1n&Aj.stnAj+1.stn)j+;/使j指向左右孩子中排序码大的孩子if(x.stn=1;i-)x=A0;/第0个元素与第i个元素交换A0=Ai;Ai=x;Sift(A,i,0);/调整A0.i-1使之为一个堆for(i=1;i=n;i+)printf(%d ,ai); printf(n);printf(n);printf(比较次数：%d次n,i);printf(移动次数：%

16、d次n,j);Void main()int i,j,n,N=20;cout 各排序方法选择结果：n;ElemTypeA20;for(j=0;jAj;cout排序前为：endl;for(i=0;iN;i+)coutAiendl;cout直接插入排序:endl;InsertSort(A,N);for(i=0;iN;i+)coutAiendl;cout选择排序:endl;SelectSort(A,N);for(i=0;iN;i+)coutAiendlcout冒泡排序:endl;BubbleSort(A,N);for(i=0;iN;i+)coutAiendl;coutShell排序:endl;Shel

17、lSort(A,N);for(i=0;iN;i+)coutAiendl;cout快速排序:endl;QuickSort(A,0,1);for(i=0;iN;i+)coutAiendl;cout堆排序:endl;HeapSort(A,N);for(i=0;iN;i+)coutAiendl;算法的时间复杂度是什么？算法的空间复杂度是什么？为什么？插入排序：稳定，时间复杂度 O(n2) O(n2)选择排序：不稳定，时间复杂度 O(n2) O(n2)冒泡排序：稳定，时间复杂度 O(n2) O(n2)希尔排序：不稳定，时间复杂度 平均时间 O(nlogn) 最差时间O(ns) 1s2 O(n2)快速排序

18、：不稳定，时间复杂度 最理想 O(nlogn) 最差时间O(n2) O(Nlogn)堆排序：不稳定，时间复杂度 O(nlog n) O(Nlogn)五、 程序调试及测试结果主要包括：选择长度为20的随机数，六种方法排序的结果。从比较次数和移动次数可大致看出各排序方法的效率高低，后三种明显优于前三种六、 结论主要包括：随机数产生方法：srand(time(0) 就是给这个算法一个启动种子，也就是算法的随机种子数，有这个数以后才可以产生随机数,用1970.1.1至今的秒数，初始化随机数种子。Srand是种下随机种子数，你每回种下的种子不一样，用Rand得到的随机数就不一样。为了每回种下一个不一样的种子，所以就选用Time(0)，Time(0)是得到当前时时间值（因为每时每刻时间是不一样的了）。进行函数的参数传递时，如果传入一个地址，比传入一个struct效率要高，因为少了一个拷贝过程。待改进的地方：很多步骤有重复用到，如把数组b赋值给a，定义Ccnt