数据结构实习报告排序.doc

数据结构课程设计实习报告 题 目：四个排序算法的比较学 号：1210522姓 名：何厚华年 级：大二学 院：计算机与控制工程学院专 业：计算机科学与技术完成日期：2014年5月25日授课教师：辛运帏目录1.题目. 22.要求 . . . . . . . . . . . . . . . . . . . . . . . . 23.程序实现 . . . . . . . . . . . . . . . . . . . . . 2 3.1程序运行及编译环境 . . . . . . . . . . . . . . . . 2 3.2程序描述 . . . . . . . . . . . . . . . . . 2 3.3实现功能 . . . . . . . . . . . . . . . . . . 3 3.3.1子功能模块 . . . . . . . . . . . . . . . . . 3 3.3.1.1 子功能模块1 . . . . . . . . . . . . . . 3 3.3.1.2子功能模块2. . . . . . . . . . . . . . . 4 3.3.1.3子功能模块3. . . . . . . . . . . . . . . 4 3.3.1.4子功能模块4. . . . . . . . . . . . . . 6 3.3.1.5子功能模块5. . . . . . . . . . . . . . . 7 3.3.1.6子功能模块6. . . . . . . . . . . . . . . 8 3.3.1.7子功能模块7. . . . . . . . . . . . . . . 9 3.3.2 数据结构. . . . . . . . . . . . . . . . . . . . 10 3.3.3算法及程序说明. . . . . . . . . . . . . . . . . . 10 3.4运行结果 . . . . . . . . . . . . . . . . . . . 12 3.5尚未解决的问题 . . . . . . . . . . . . . . . . . . 151. 题目 四个排序算法的比较给定N个int类型（自定义N的上限M，例如M=100000，N的取值不能少于10000）的整数，分别使用插入排序、快速排序、希尔排序和堆排序方法进行升序排序。具体要求：1 四种排序方法均能得到正确的排序结果。2 分别统计四种排序中关键字比较的次数和记录交换的次数，并将统计结果显示出来。 2.要求：初始数据使用随机数发生器产生，并使用程序自动检验排序结果的正确性。同时，需要编写一个检验随机性的小测试程序，分别统计各数段间数据的个数。数段的划分自定。例如可以按1000为一单位，分别统计（0，999）、（1000，1999）、（N-1000，N-1）之间的数据个数。如果N较大，也可以按10000为一单位。总之，只要能说明问题即可。在一个数段内，还可以再分析各子数段中数据的个数，例如选定（1000，1999）数段，然后以100为一单位，统计这10个子数段中的数据个数。3. 程序实现 3.1程序运行及编译环境程序是用Visual Studio 2010即VS10.0 编译的。可以在windows系列的操作系统上运行。 3.2程序描述 该程序主要用于实现了插入排序，希尔排序，快速排序和堆排序的算法，然后比较各种算法在系统产生的上万个随机数下排序的各种参数，这些参数主要有：比较次数，移动次数，交换次数，排序耗时。然后，验证了每一种排序结果的正确性，最后，统计了随机数组的分布情况，以判断系统产生的随机数是否均匀。其流程如下：A).产生上万个随机数，并处理成满足范围条件的随机数B).依次进行插入排序，希尔排序，快速排序，堆排序并且获得它们的主要参数C).验证排序结果的正确性D).统计随机数的区间分布E).完成3.3实现功能A. 统计随机数的区间分布B. 检验排序结果的正确性C. 实现插入排序算法D. 实现希尔排序算法E. 实现快速排序算法F. 实现建堆，整堆算法G. 在建堆，整堆的基础上实现堆排序的算法3.3.1 子功能模块3.3.1.1 子功能模块1/*函数原型：void RandomTest(int a,int n);函数参数：a表示测试的数组，n表示数组元素个数函数功能：随机性检测，把它们分到50个区间里面去*/void RandomTest(int a,int n)int interval=MAXIMUM/INTERVALCOUNT;int CountINTERVALCOUNT;for(int i=0;iINTERVALCOUNT;i+)Counti=0;for(int i=0;in;i+)Countai/interval+;/把这个数加入到对应的区间中去cout统计结果如下：endl区间 个数endl;for(int i=0;iINTERVALCOUNT;i+)coutsetw(5)i*interval,setw(6)(i+1)*interval)setw(6)Countiendl;3.3.1.2子功能模块2/*函数原型：bool IsOrder(int a,int n,bool IsReverse=false)；函数参数：int a表示待判断的数组 int n表示数组的前n项 bool IsReverse=false，表示这个数组按照升序还是反序排列，默认为升序函数功能：用于判断排序结果的正确性*/bool IsOrder(int a,int n,bool IsReverse=false)/true,表降序,false,表升序switch (IsReverse)case true:for(int i=1;in-1;i+)if(aiai+1)cout排序有误！请检查排序算法！endl;/检测到有逆序排列的/couti ai i+1 ai+1endl;return false;cout恭喜你，排序算法成功！endl;return true;case false:return true;3.3.1.3子功能模块3/*函数原型：void InsertSort(int a,int &Compare,int& Swap,int& Move,float& time,int n=MAXCOUNT)；函数参数：a表示待排序的数组 Compare表示比较的次数 Swap表示交换次数 Move表示移动次数 time表示执行时间 n表示数组大小函数功能：插入排序*/void InsertSort(int a,int &Compare,int& Swap,int& Move,float& time,int n=MAXCOUNT)int i,j;clock_t finish,start=clock();/开始计时Compare=Swap=Move=0;/初始化几个变量for(i=2;i0;j-)/从后往前比较if(aja0)aj+1=aj;Compare+;Move+;elseCompare+;break;aj+1=a0;/找到合适位置finish=clock();/完成计时time+=1000*(finish-start);3.3.1.4子功能模块4/*函数原型：void ShellSort(int a,int &Compare,int& Swap,int& Move,float& time,int n=MAXCOUNT)；函数参数：a表示排序数组 Compare：比较次数 Swap：交换次数 Move：移动次数 time：运行时间 n：数组元素个数函数功能：希尔排序，依次设置增量分组，然后组内进行插入排序*/void ShellSort(int a,int &Compare,int& Swap,int& Move,float& time,int n=MAXCOUNT)int i,j,d;clock_t finish,start=clock();d=D;/最初的分组Compare=Swap=Move=0;cout希尔排序增量序列为：0)/只要分组大于0就循环for(i=d+1;i0;j=j-d)/每间隔d个作为一组if(aja0)aj+d=aj;Compare+;Move+;elseCompare+;break;aj+d=a0;if(d!=1)/输出希尔排序增量序列coutd,;elsecoutdendl;d/=2;/每次增量减半finish=clock();time+=(1000*(finish-start);3.3.1.5子功能模块5/*函数原型：void QuickSort(int a,int left,int right,int& Compare,int& Swap,int& Move,float& time)；函数参数：a表示排序数组 left表示左边区间起点 right表示右边区间起点 Compare：比较次数 Swap：交换次数 Move：移动次数 time：运行时间函数功能：快速排序*/void QuickSort(int a,int left,int right,int& Compare,int& Swap,int& Move,float& time)int i=left,j=right;clock_t finish,start=clock();a0=aleft;/a0不参与排序，枢轴放在这个位置while(ij)/左边指针小于右边指针时while(ia0)j-;Compare+;/右边的比枢轴大if(ij) ai+=aj;Move+;/右边得到一个比枢轴小或者等于枢轴的数据while(ij&ai=a0)i+;Compare+;/左边的比枢轴小if(ileft) QuickSort(a,left,j,Compare,Swap,Move,time);/对左边快排if(iright) QuickSort(a,i,right,Compare,Swap,Move,time);/对右边快排finish=clock();time=1000*(finish-start);3.3.1.6子功能模块6/*函数原型：void Heap(int a,int i,int m,int& Compare,int& Swap,int& Move)；函数参数：函数参数：a表示待整成堆的数组 i表示根节点的编号 m表示以i为根节点的最后一个结点的编号 Compare：比较次数 Swap：交换次数 Move：移动次数函数功能：整堆函数，从以i为编号的根节点开始，直到最底层*/void Heap(int a,int i,int m,int& Compare,int& Swap,int& Move)int j;a0=ai;/j=2*i;while(j=m)if(jm&aja0)/比双亲结点大Compare+;ai=aj;/孩子赋值给父节点Move+;i=j;j=2*i;/向下层探测elsej=m+1;/强制结束循环ai=a0;/最合适的位置3.3.1.7子功能模块7/*函数原型：void HeapSort(int a,int& Compare,int& Swap,int& Move,float& time,int n=MAXCOUNT)；函数参数：a表示排序数组 Compare：比较次数 Swap：交换次数 Move：移动次数 time：运行时间 n:堆的大小函数功能：堆排序*/void HeapSort(int a,int& Compare,int& Swap,int& Move,float& time,int n=MAXCOUNT)clock_t finish,start=clock();int i;for(i=n/2;i=1;i-) Heap(a,i,n,Compare,Swap,Move);/初始建堆过程，从倒数第二层开始整堆，直到根节点，建堆完成for(i=n;i=2;i-)/取出最大的那个元素a0=a1;a1=ai;ai=a0;Swap+;Heap(a,1,i-1,Compare,Swap,Move);/取出最大的那个元素后，从1开始整堆finish=clock();time+=1000*(finish-start);3.3.2 数据结构/*这个结构用于存储每一个排序的一些参数*/typedef struct SortResultchar* Name;/排序方法int compare;/比较次数int swap;/交换次数int move;/移动次数float time;/运行时间;3.3.3算法及程序说明本程序中重要的算法思想是：1. 由于插入排序等每一次的交换都可以通过一次一次的移动来完成，而交换一次相当于移动3次，因此，插入排序中能不交换则不交换，交换一律用等量的移动来替代，故插入排序里面的交换次数为0.2.由于计算机是图灵机，就是说，相同的输入必会产生相同的输出，因此，系统提供的随机数并不是真正意义上的随机数，而是伪随机序列，并且这个序列有个最大值32767，这个数并不满足题设的要求，所以做了一些处理。处理思想如下：刚刚开始时，试图通过平方每个随机数来做取模运算来扩大这个随机数的范围，并且看似达到了目的，但是这样的随机数并不能连续，换句话说，就是有一些数永远也产生不了，因为从0到32767这32768个数里面，一个数的平方然后取模只能对应一个唯一的数，因此这种方法仅能产生从032767*32767mod(MAXIMUN)的随机数32768个，所以这种方法仅仅是外表上的，而有很多数实际上是永远也取不到的。经过改善后，可以取到032767*32767mod(MAXIMUN)的任意一个自然数。随机数的产生以及处理方法如下：for(int i=1;iMAXCOUNT;i+)/系统初始产生的随机数num=rand()*rand()%MAXIMUM;ai=bi=ci=di=num;cout参与排序的随机数有MAXCOUNT个,其理论范围是：0MAXIMUM;/随机数个数以及范围for(int i=1;iai)a0=ai;for(int i=1;iMAXCOUNT;i+)if(b0bi)b0=bi;cout其实际范围为：a0b0endl;从处理后统计的结果来看，随机数的分布还是相对均匀的。3. 关于希尔排序的增量序列的取法，为了达到每次排序的序列都尽可能不重复的目的，本程序的增量序列为2的幂次减1，这样，这个增量序列的任意两个数均不可约，并且可以由运算d=d/2;来自动完成增量的选取。如本程序的增量序列为：65535,32767,16383,8191,4095,2047,1023,511,255,127,63,31,15,7,3,1.4. 本人对堆排序的理解：堆排序是对一般的选择排序的改进，一般的选择排序在选择的过程中尽管进行了很多比较，但是这些比较的结果并没有保存下来，以至于后来还需要比较已经比较过的数据对，造成了浪费，为了减少这种浪费，堆排序可以保存一部分比较的结果，所以比选择排序要快。3.4运行结果图1. 用四种方法处理无序的随机数序列的结果从这些数据可以看到，插入排序比较次数和移动次数最多，耗时也是最多的，并且要远多于其他三种算法；希尔排序作为插入排序的一种改进，能大大减少比较次数和移动次数，时间消耗大大减少；快速排序比较操作和移动操作以及时间消耗都是这几种算法里面最少的；