七种排序算法的比较及每种排序的上机统计时间

《数据结构》课程设计报告课题:排序算法的比较学院:信息学院班级:2011级电子信息工程1班小组成员:韦志东（组长）20111601310027夏琪20111601310028完成时间:2014-01-08教师:周铁1目录1、课程分析..........................................................21.1、选题..........................................................................................................21.2、选题的意义及背景..................................................................................21.3、设计任务书………………………………………………………………22、设计分析..........................................................22.1、原始数据..................................................................错误!未定义书签。2.2、输出数据..................................................................错误!未定义书签。2.3、程序流程图..............................................................................................33、程序源代码及注释..................................................34、测试结果..........................................错误!未定义书签。5、总结.............................................................266、参考文献.........................................................277、小组人员分工.....................................................2721、课程分析1.1、选题要求利用随机函数产生30000个随机整数，利用直接插入排序、希尔排序，冒泡排序、直接选择排序、快速排序、堆排序、归并排序的排序方法进行排序，并统计每一种排序上机所花费的时间。1.2、选题的意义及背景排序是计算机程序设计中的一种重要操作，它的功能是将一个数据元素的任意序列，重新排列成一个按关键词有序的序列。此实验通过对各种内部排序算法进行比较，能使我们更好的掌握各种排序的基本思想，掌握各种排序方法的算法实现，掌握各种排序方法的优劣分析及花费的时间的计算，掌握各种排序方法所适应的不同场合。通过该题目的设计，可以加深理解各种数据结构的逻辑结构、存储结构及相应上运算的实现，进一步理解和熟练掌握课本中所学的各种数据结构，学会如何把学到的知识用于解决实际问题，培养我们的动手能力。1.3、设计任务书（1）定义结构体，头文件，定义数组范围，大小。（2）依次描写七种排序的算法。（3）描写产生随机函数的算法。（4）描写菜单函数。（5）描写主函数，调用七种排序的算法。2、设计分析2.1原始资料用户输入记录的个数30000个，数据由随机函数生成。2.2输出数据产生的随机数分别用冒泡排序、直插排序、希尔排序、选择排序、快速排序、堆排序、归并排序这些排序方法进行排序，并统计每一种排序上机所花费的时间。32.3程序流程图3．程序源代码及其注释#includestdio.h#includestdlib.h#includemath.h#includetime.h#includeconio.h#defineMAX60000/*记录数组的个数*/#defineNUM30000/*实际输入数组的个数*/主程序产生1组随机数将随机数保存在数组中直接插入排序冒泡排序直接选择排序二路归并排序堆排序快速排序Shell排序输出排序上机所花费的时间4typedefintdatatype;typedefstruct/*定义记录为结构体类型*/{intkey;/*记录的关键词域*/datatypeother;/*记录的其它域*/}rectype;rectype*s1,s[MAX];/*s[MAX]存放原始随机数，*s1取出原始数据后进行排序*//*直接插入排序算法如下*/voidinsert_sort(rectype*r)/*对数组r按递增顺序进行插入排序算法*/{inti,j,n=NUM;/*NUM为实际输入的记录数，是一个常量*/for(i=1;i=n;i++)/*iNUM条件很重要，NUM为实际记录数*/{r[0]=r[i];/*r[0]为监视哨*/j=i-1;/*依次插入记录r[1],……，r[NUM]*/while(r[0].keyr[j].key)/*查找r[i]合适的位置*/{r[j+1]=r[j--];}/*将记录关键词大于r[i].key的记录后移*/r[j+1]=r[0];/*将记录r[i]插入到有序表的合适的位置上*/}}/*INSERTSORT*//*希尔排序算法如下*/voidshell_sort(rectype*r)/*取增量为d(i+1)=[d(i)/2]的希尔排序的算法*/{inti,n,jump,change,temp,m;/*change为交换标志，jump为增量步长*/jump=NUM;n=NUM;/*NUM为顺序表的实际长度*/while(jump0){jump=jump/2;/*取步长d(i+1)=[d(i)/2]*/do{change=0;/*设置交换标志，change=0表示未交换*/for(i=1;i=n-jump;i++){m=i+jump;/*取本趟的增量*/if(r[i].keyr[m].key)/*记录交换*/5{temp=r[m].key;r[m].key=r[i].key;r[i].key=temp;change=1;/*change=1表示有交换*/}/*if*/}/*for*//*本趟排序完成*/}while(change==1);/*当change=0时终止本趟排序*/}/*while*//*当增量jump=1且change=0时终止算法*/}/*SHELLSORT*//*冒泡排序算法如下*/voidbubble_sort(rectype*r)/*从下往上扫描的冒泡排序*/{inti,j,noswap=0,n=NUM;/*noswap为交换标志,NUM为实际输入记录数*/rectypetemp;for(i=1;in;i++)/*进行n-1趟冒泡排序*/{noswap=1;/*设置交换标志，noswap=1表示没有记录交换*/for(j=n;j=i;j--)/*从下往上扫描*/if(r[j].keyr[j-1].key)/*交换记录*/{temp.key=r[j-1].key;r[j-1].key=r[j].key;r[j].key=temp.key;noswap=0;/*当交换记录时，将交换标志置0即noswap=0*/}/*if*/if(noswap)break;/*若本趟排序中未发生记录交换，则终止排序*/}/*for*//*终止排序算法*/}/*BUBBLESORT*//*快速排序算法如下*/intpartition(rectype*r,ints,intt)/*快速排序算法中的一趟划分函数*/{inti,j;rectypetemp;6i=s;j=t;temp=r[i];/*初始化，temp为基准记录*/do{while((r[j].key=temp.key)&&(ij))j--;/*从右往左扫描，查找第一个关键词小于temp的记录*/if(ij)r[i++]=r[j];/*交换r[i]和r[j]*/while((r[i].key=temp.key)&&(ij))i++;/*从左往右扫描，查找第一个关键词大于temp的记录*/if(ij)r[j--]=r[i];/*交换r[i]和r[j]*/}while(i!=j);/*i=j,z则一次划分结束，基准记录达到其最终位置*/r[i]=temp;/*最后将基准记录temp定位*/return(i);}/*PARTITION*/voidquick_sort(rectype*r,inths,intht)/*对r[hs]到r[ht]进行快速排序*/{inti;if(hsht)/*只有一个记录或无记录时无需排序*/{i=partition(r,hs,ht);/*对r[hs]到r[ht]进行一次划分*/quick_sort(r,hs,i-1);/*递归处理左区间*/quick_sort(r,i+1,ht);/*递归处理右区间*/}}/*QUICK_SORT*//*直接选择排序算法如下*/voidselect_sort(rectype*r){rectypetemp;inti,j,k,n=NUM;/*NUM为实际输入记录数*/for(i=1;i=n;i++)/*做n-1趟选择排序*/{k=i;for(j=i+1;j=n;j++)/*在当前无序区中选择关键词最小的记录r[k]*/if(r[j].keyr[k].key)k=j;if(k!=i){temp=r[i];/*交换记录r[i]和r[k]*/r[i]=r[k];7r[k]=temp;}}/*for*/}/*SELECT_SORT*//*堆排序算法如下*/voidshift(rectype*r,inti,intm)/*堆的筛选算法,在数组中r[i]到r[m]中，调整堆r[i]*/{intj;rectypetemp;temp=r[i];j=2*i;while(j=m)/*j=m,r[2*i]是r[i]的左孩子*/{if((jm)&&(r[j].keyr[j+1].key))j++;/*j指向r[i]的左右孩子中关键词较大者*/if(temp.keyr[j].key)/*若孩子结点的关键词大于父结点*/{r[i]=r[j];/*将r[j]调到父亲结点的位置上*/i=j;/*调整i和j的值，以便继续“筛”结点*/j=2*i;}elsej=m+2;/*调整完毕，退出循环*/}r[i]=temp;/*将被筛选的结点放入正确的位置*/}/*SHIFT*/voidheap_sort(rectype*r)/*对数组r[1]到r[NUM]进行堆排序*/{rectypetemp;inti,n;n=NUM;/*NUM为数组的实际长度*/for(i=n/2;i0;i--)/*建立初始堆*/shift(r,i,n);for(i=n;i1;i--)/*进行n-1趟筛选，交换，调整，完成堆排序*/8{temp=r[1];/*将堆顶元素r[1]与最后一个元素交换位置*/r[1]=r[i];r[i]=temp;shift(r,1,i-1);/*将数组元素r[1]到r[i-1]重新调整成为一个新堆*/}/*FOR*/}/*HEAP_SORT*//*二路归并排序算法如下*/voidmerge(rectype*a,rectype*r,intlow,intmid,inthigh){inti,j,k;i=low;j=mid+1;k=low;while((i=mid)&&(j=high))/*将两个相邻有序子表进行合并*/{if(a[i].key=a[j].key)/*取两表中小者复制*/r[k++]=a[i++];elser[k++]=a[j++];}while(i=mid)