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

资源描述

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

《时间管理七种排序算法的比较及每种排序的上机统计时间.docx》由会员分享，可在线阅读，更多相关《时间管理七种排序算法的比较及每种排序的上机统计时间.docx（12页珍藏版）》请在冰点文库上搜索。

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

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

（时间管理）七种排序算法

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

《数据结构》课程设计方案

课题:

排序算法的比较

学院:

信息学院

班级:

2011级电子信息工程1班

小组成员:

韦志东（组长）227夏琪228

完成时间:

2014-01-08教师:

周铁

1、课程分析2

1.1、选题2

1.2、选题的意义及背景2

1.3、设计任务书…2

2、设计分析2

2.1、原始数据2

2.2、输ft数据2

2.3、程序流程图3

3、程序源代码及注释3

4、测试结果12

5、总结26

6、参考文献27

7、小组人员分工27

1、课程分析

1.1、选题要求

利用随机函数产生30000个随机整数,利用直接插入排序、希尔排序,冒泡排序、直接选择排序、快速排序、堆排序、归且排序的排序方法进行排序,且统计每壹种排序上机所花费的时间。

1.2、选题的意义及背景

排序是计算机程序设计中的壹种重要操作,它的效用是将壹个数据元素的任意序列,重新排列成壹个按关键词有序的序列。

此实验通过对各种内部排序算法进行比较,能使我们更好的掌握各种排序的基本思想,掌握各种排序方法的算法实现,掌握各种排序方法的优劣分析及花费的时间的计算,掌握各种排序方法所适应的不同场合。

通过该题目的设计,能够加深理解各种数据结构的逻辑结构、存储结构及相应上运算的实现,进壹步理解和熟练掌握课本中所学的各种数据结构,学会如何把学到的知识用于解决实际问题,培养我们的动手能力。

1.3、设计任务书

（1）定义结构体,头文件,定义数组范围,大小。

（2）依次描写七种排序的算法。

（3）描写产生随机函数的算法。

（4）描写菜单函数。

（5）描写主函数,调用七种排序的算法。

2、设计分析

2.1原始资料

用户输入记录的个数30000个,数据由随机函数生成。

2.2输ft数据

产生的随机数分别用冒泡排序、直插排序、希尔排序、选择排序、快速排序、堆排序、归且排序这些排序方法进行排序,且统计每壹种排序上机所花费的时间。

2.3程序流程图

2.4

3．程序源代码及其注释

#include"stdio.h"

#include"stdlib.h"

#include"math.h"

#include

#defineMAX60000/*记录数组的个数*/

#defineNUM30000/*实际输入数组的个数*/typedefintdatatype;

typedefstruct/*定义记录为结构体类型*/

{intkey;/*记录的关键词域*/

datatypeother;/*记录的其它域*/

}rectype;

rectype*s1,s[MAX];/*s[MAX]存放原始随机数,*s1取ft原始数据后进行排序*/

/*直接插入排序算法如下*/

voidinsert_sort（rectype*r）/*对数组r按递增顺序进行插入排序算法*/

{inti,j,n=NUM;/*NUM为实际输入的记录数,是壹个常量*/

for（i=1;i<=n;i++）/*i

{r[0]=r[i];/*r[0]为监视哨*/

j=i-1;/*依次插入记录r[1],……,r[NUM]*/

while（r[0].key

{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（jump>0）

{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].key>r[m].key）/*记录交换*/

{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,nos*noswap为交换标志,NUM为实际输入记录数*/rectypetemp;

for（i=1;i

{nos*设置交换标志,noswap=1表示没有记录交换*/for（j=n;j>=i;j--）/*从下往上扫描*/

if（r[j].key

{temp.key=r[j-1].key;

r[j-1].key=r[j].key;r[j].key=temp.key;

nos*当交换记录时,将交换标志置0即noswap=0*/

}/*if*/

if（nos*若本趟排序中未发生记录交换,则终止排序*/

}/*for*//*终止排序算法*/

}/*BUBBLESORT*/

/*快速排序算法如下*/

intpartition（rectype*r,ints,intt）/*快速排序算法中的壹趟划分函数*/

{inti,j;rectypetemp;

i=s;j=t;temp=r[i];/*初始化,temp为基准记录*/do{while（（r[j].key>=temp.key）&&（i

j--;/*从右往左扫描,查找第壹个关键词小于temp的记录*/

if（i

i++;/*从左往右扫描,查找第壹个关键词大于temp的记录*/if（i

}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（hs

{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].key

if（k!

=i）{temp=r[i];/*交换记录r[i]和r[k]*/r[i]=r[k];

r[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（（j

j++;/*j指向r[i]的左右孩子中关键词较大者*/

if（temp.key

{r[i]=r[j];/*将r[j]调到父亲结点的位置上*/

i=j;/*调整i和j的值,以便继续“筛”结点*/j=2*i;

}

else

j=m+2;/*调整完毕,退ft循环*/

}

r[i]=temp;/*将被筛选的结点放入正确的位置*/

}/*SHIFT*/

voidheap_sort（rectype*r）/*对数组r[1]到r[NUM]进行堆排序*/

{rectypetemp;inti,n;

n=NUM;/*NUM为数组的实际长度*/for（i=n/2;i>0;i--）/*建立初始堆*/shift（r,i,n）;

for（i=n;i>1;i--）/*进行n-1趟筛选,交换,调整,完成堆排序*/

{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）r[k++]=a[i++];/*复制第壹个有序子表的剩余记录*/

while（j<=high）r[k++]=a[j++];/*复制第二个有序子表的剩余记录*/

}/*MERGE*/voidmerge_pass（rectype*r,rectype*r1,intlength）

{inti=1,j,n=NUM;

while（（i+2*length-1）<=n）/*归且若干长度为2*length的俩个相邻有序子表*/

{merge（r,r1,i,i+length-1,i+2*length-1）;

i=i+2*length;/*i指向下壹对有序子表的起点*/

}

if（i+length-1

merge（r,r1,i,i+length-1,n）;/*处理表长不足2*length的部分*/elsefor（j=i;j<=n;j++）

r1[j]=r[j];/*将最后壹个子表复制到r1中*/

}/*MERGEPASS*/

voidmerge_sort（rectype*r）

{intlength;rectyper1[MAX];

length=1;/*归且长度从1开始*/while（length

{merge_pass（r,r1,length）;/*壹趟归且,结果存放于r1中*/

length=2*length;/*归且后有序表的长度加倍*/

merge_pass（r1,r,length）;/*再次归且,结果存放于r中*/

length=2*length;/*再次将归且后有序表的长度加倍*/

}

}/*MERGE_SORT*/

voidcreat_randnum（int*a）/*产生给定个数和范围的随机整数函数*/

{inti;intrange=30000;srand（time（NULL））;for（i=1;i<=NUM;i++）

{a[i]=rand（）;}/*调用rand生成随机整数*/

printf（"\n\n\t\t\t排序前的原始随机整数为:

\n\n\t"）;for（i=1;i<=NUM;i++）

{printf（"%6d",a[i]）;/*输ft随机整数*/if（i%10==0）printf（"\n\t"）;

}printf（"\n"）;

}/*CREAT_RANDNUM*/

voidcreate（）/*产生NUM个随机整数且保存到记录数组s中*/

{intb[MAX];intrange=30000,i;

creat_randnum（b）;/*调用随机整数生成函数,结果存放于数组b中*/for（i=1;i<=NUM;i++）

s[i].key=b[i];/*将随机整数存放到数组s中*/

s1=s;/*s1指向s,以便保存原始数据*/

}/*CREAT*/

voidprint_record（rectype*r）/*记录数组的输ft函数*/

{inti;

printf（"\n\t\t\t排序后的有序随机整数:

\n\n\t"）;for（i=1;i<=NUM;i++）

{printf（"%6d",r[i].key）;if（i%10==0）printf（"\n\n\t"）;

}getchar（）;getchar（）;

}/*PRINTRECORD*/

intmenu_select（）/*主菜单选择模块*/

{charc;intkk;

system（"cls"）;/*清屏函数*/

printf（"内排序算法的比较----主控模块:

\n\n"）;

printf（"\t\t\t1.直接插入排序\n"）;

printf（"\t\t\t2.希尔排序\n"）;

printf（"\t\t\t3.冒泡排序\n"）;

printf（"\t\t\t4.快速排序\n"）;

printf（"\t\t\t5.直接选择排序\n"）;

printf（"\t\t\t6.堆排序\n"）;

printf（"\t\t\t7.二路归且排序\n"）;

printf（"\t\t\t0.退ft\n"）;

do{printf（"\n\t\t\t请按数位0—7键选择效用:

"）;c=getchar（）;kk=c-48;

}while（（kk<0）||（kk）>7）;return（kk）;

}/*MENU_SELECT*/

main（）/*算法比较--主程序模块*/

{

doubletime1,time2,time3,time4,time5,time6,time7;clock_tstart,finish;

intkk;

do{kk=menu_select（）;/*进入主菜单选择模块*/

if（kk!

=0）create（）;/*建立记录数组*/switch（kk）

{case1:

{start=clock（）;insert_sort（s1）;finish=clock（）;

time1=（double）（finish-start）/CLOCKS_PER_SEC;

printf（"直接插入排序耗时%fseconds\n",time1）;break;}case2:

{start=clock（）;

shell_sort（s1）;finish=clock（）;

time2=（double）（finish-start）/CLOCKS_PER_SEC;

printf（"希尔排序耗时%fseconds\n",time2）;break;}case3:

{start=clock（）;

bubble_sort（s1）;finish=clock（）;

time3=（double）（finish-start）/CLOCKS_PER_SEC;

printf（"冒泡排序耗时%fseconds\n",time3）;break;}case4:

{start=clock（）;

quick_sort（s1,1,NUM）;finish=clock（）;

time4=（double）（finish-start）/CLOCKS_PER_SEC;

printf（"快速排序耗时%fseconds\n",time4）;break;}case5:

{start=clock（）;

select_sort（s1）;finish=clock（）;

time5=（double）（finish-start）/CLOCKS_PER_SEC;

printf（"直接选择排序耗时%fseconds\n",time5）;break;}case6:

{start=clock（）;

heap_sort（s1）;finish=clock（）;

time6=（double）（finish-start）/CLOCKS_PER_SEC;

printf（"堆排序耗时%fseconds\n",time6）;break;}case7:

{start=clock（）;

merge_sort（s1）;finish=clock（）;

time7=（double）（finish-start）/CLOCKS_PER_SEC;

printf（"二路归且排序耗时%fseconds\n",time7）;break;}case0:

{exit（0）;}

}print_record（s1）;

}while（kk!

=0）;

}/*MAIN*/

4．测试结果

（1）选择直接插入排序：

排序前本有30000个随机数显示,但数据太多,只截壹部分图来表示。