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

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

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

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

Documentserialnumber【UU89WT-UU98YT-UU8CB-UUUT-UUT108】

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

《数据结构》课程设计报告

课题:

排序算法的比较

学院:

信息学院

班级:

2011级电子信息工程1班

小组成员:

韦志东（组长）

夏琪

完成时间:

2014-01-08

*****

、设计任务书………………………………………………………………2

27

27

1、课程分析

、选题要求

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

、选题的意义及背景

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

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

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

、设计任务书

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

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

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

（4）描写菜单函数。

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

2、设计分析

原始资料

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

输出数据

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

程序流程图

3．程序源代码及其注释

#include""

#include""

#include""

#include<>

#include<>

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

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

typedefintdatatype;

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++）/*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,noswap=0,n=NUM;/*noswap为交换标志,NUM为实际输入记录数*/

rectypetemp;

for（i=1;i

{noswap=1;/*设置交换标志，noswap=1表示没有记录交换*/

for（j=n;j>=i;j--）/*从下往上扫描*/

if（r[j].key

{=r[j-1].key;

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

r[j].key=;

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

}/*if*/

if（noswap）break;/*若本趟排序中未发生记录交换，则终止排序*/

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

}/*BUBBLESORT*/

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

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

{inti,j;rectypetemp;

i=s;j=t;temp=r[i];/*初始化，temp为基准记录*/

do{while（（r[j].key>=&&（i

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

if（i

while（（r[i].key<=&&（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

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

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

j=2*i;

}

else

j=m+2;/*调整完毕，退出循环*/

}

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]）;/*输出随机整数*/

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）/*记录数组的输出函数*/

{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.退出\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个随机数显示，但数据太多，只截一部分图来表示。

排序后也一样，应有30000个排好顺序的整数显示，但由于数据过多，也只截一部分图来表示。

由图可知，直接插入排序耗时秒

（2）选择希尔排序：

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

排序后也一样，应有30000个排好顺序的整数显示，但由于数据过多，也只截一部分图来表示。

由图可知，希尔排序耗时秒

（3）选择冒泡排序：

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

排序后也一样，应有30000个排好顺序的整数显示，但由于数据过多，也只截一部分图来表示。

由图可知，冒泡排序耗时秒

（4）选择快速排序：

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

排序后也一样，应有30000个排好顺序的整数显示，但由于数据过多，也只截一部分图来表示。

由图可知，快速排序耗时秒

（5）选择直接选择排序：

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

排序后也一样，应有30000个排好顺序的整数显示，但由于数据过多，也只截一部分图来表示。

由图可知，直接选择排序耗时秒

（6）选择堆排序：

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

排序后也一样，应有30000个排好顺序的整数显示，但由于数据过多，也只截一部分图来表示。

由图可知，堆排序耗时秒

（7）选择二路归并排序：

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

排序后也一样，应有30000个排好顺序的整数显示，但由于数据过多，也只截一部分图来表示。

由图可知，二路归并排序耗时秒

5.总结与体会

总结：

由上述比较我们可以清楚地知道，各种排序算法之间的差别是很大的。

其中在这几种不同的算法中，快速排序是其中最快的一种排序算法，其它几种算法都有些差异，其中冒泡排序最慢。

通过实验设计，我们可以明确感受一些内部排序方法选择的规则，其主要是

（1）当n较小时：

可采用直接插入排序和直接选择排序；

（2）当记录规模小时，可选择直接插入排序；当记录规模大时，可选择直接选择排序，因为直接插入排序所需的记录移动操作比直接选择排序多；（3）当记录基本有序时：

可采用直接插入排序和冒泡排序；（4）当n较大时：

可采用快速排序和归并排序。

体会：

通过此次的课程设计，让我从中得到了许多锻炼，也学到了许多东西。

通过对排序算法的比较的设计，我更加深入地理解了算法的思想与原理，也深切地感受各种算法的运行时间长短，体会到它的优缺点，并且充分锻炼了我的动手能力，把理论与实践相结合，把学到的知识用于解决实际的问题。

而且，通过设计的操作，让我体会到了一个人力量的渺小，充分感受到了团队协作的力量，大家一起相互讨论，积极沟通，相互学习，相互帮助，锻炼了我的协作能力。

还有对于编程来说，让我体会到了看书很重要，但实在在动手去做才是硬道理，特别在调试的时候，要有足够的耐心与亲自不断尝试的能力，还有编程一定养成良好的编程习惯，无论命名还是结构。

尽管还有很多地方有待提高和改正，不管怎样通过此次的课程设计我受益匪浅，积累了经验，锻炼了自己分析问题、解决问题的能力。

6.参考文献

[1]秦锋、袁志祥.数据结构（C语言版）例题详解与课程设计指导.北京：

清华大学出版社

[2]XX文库

[3].严蔚敏，吴伟民，《数据结构（C语言版）》，清华大学出版社,2009

7.小组人员分工

组长：

韦志东

组员：

夏琪

分工：

韦志东：

主程序、随机函数生产、报告撰写

夏琪：

直接插入排序，希尔排序，冒泡排序，直接选择，，快速排序，堆排序，归并排序，数据记录。