七种排序算法的比较及每种排序的上机统计时间Word文件下载.docx
《七种排序算法的比较及每种排序的上机统计时间Word文件下载.docx》由会员分享，可在线阅读，更多相关《七种排序算法的比较及每种排序的上机统计时间Word文件下载.docx（31页珍藏版）》请在冰点文库上搜索。
conio.h>
#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<
NUM条件很重要，NUM为实际记录数*/
{r[0]=r[i];
/*r[0]为监视哨*/
j=i-1;
/*依次插入记录r[1],……，r[NUM]*/
while（r[0].key<
r[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（jump>
0）
{jump=jump/2;
/*取步长d（i+1）=[d（i）/2]*/
do{change=0;
/*设置交换标志，change=0表示未交换*/
=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;
n;
i++）/*进行n-1趟冒泡排序*/
{noswap=1;
/*设置交换标志，noswap=1表示没有记录交换*/
for（j=n;
j>
=i;
j--）/*从下往上扫描*/
if（r[j].key<
r[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;
i=s;
j=t;
temp=r[i];
/*初始化，temp为基准记录*/
do{while（（r[j].key>
=temp.key）&
&
（i<
j））
j--;
/*从右往左扫描，查找第一个关键词小于temp的记录*/
if（i<
j）r[i++]=r[j];
/*交换r[i]和r[j]*/
while（（r[i].key<
i++;
/*从左往右扫描，查找第一个关键词大于temp的记录*/
j）r[j--]=r[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<
ht）/*只有一个记录或无记录时无需排序*/
{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为实际输入记录数*/
i++）/*做n-1趟选择排序*/
{k=i;
for（j=i+1;
j<
j++）/*在当前无序区中选择关键词最小的记录r[k]*/
r[k].key）k=j;
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<
m）&
（r[j].key<
r[j+1].key））
j++;
/*j指向r[i]的左右孩子中关键词较大者*/
if（temp.key<
r[j].key）/*若孩子结点的关键词大于父结点*/
{r[i]=r[j];
/*将r[j]调到父亲结点的位置上*/
i=j;
/*调整i和j的值，以便继续“筛”结点*/
else
j=m+2;
/*调整完毕，退出循环*/
r[i]=temp;
/*将被筛选的结点放入正确的位置*/
}/*SHIFT*/
voidheap_sort（rectype*r）/*对数组r[1]到r[NUM]进行堆排序*/
inti,n;
/*NUM为数组的实际长度*/
for（i=n/2;
i>
0;
i--）/*建立初始堆*/
shift（r,i,n）;
for（i=n;
1;
i--）/*进行n-1趟筛选，交换，调整，完成堆排序*/
{temp=r[1];
/*将堆顶元素r[1]与最后一个元素交换位置*/
r[1]=r[i];
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<
n）
merge（r,r1,i,i+length-1,n）;
/*处理表长不足2*length的部分*/
elsefor（j=i;
j++）
r1[j]=r[j];
/*将最后一个子表复制到r1中*/
}/*MERGEPASS*/
voidmerge_sort（rectype*r）
{intlength;
rectyper1[MAX];
length=1;
/*归并长度从1开始*/
while（length<
NUM）
{merge_pass（r,r1,length）;
/*一趟归并，结果存放在r1中*/
length=2*length;
/*归并后有序表的长度加倍*/
merge_pass（r1,r,length）;
/*再次归并，结果存放在r中*/
/*再次将归并后有序表的长度加倍*/
}/*MERGE_SORT*/
voidcreat_randnum（int*a）/*产生给定个数和范围的随机整数函数*/
intrange=30000;
srand（time（NULL））;
=NUM;
{a[i]=rand（）;
}/*调用rand生成随机整数*/
printf（"
\n\n\t\t\t排序前的原始随机整数为:
\n\n\t"
）;
{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中*/
s[i].key=b[i];
/*将随机整数存放到数组s中*/
s1=s;
/*s1指向s,以便保存原始数据*/
}/*CREAT*/
voidprint_record（rectype*r）/*记录数组的输出函数*/
\n\t\t\t排序后的有序随机整数:
{printf（"
r[i].key）;
}getchar（）;
getchar（）;
}/*PRINTRECORD*/
intmenu_select（）/*主菜单选择模块*/
{charc;
intkk;
system（"
cls"
/*清屏函数*/
内排序算法的比较----主控模块:
\n\n"
\t\t\t1.直接插入排序\n"
\t\t\t2.希尔排序\n"
\t\t\t3.冒泡排序\n"
\t\t\t4.快速排序\n"
\t\t\t5.直接选择排序\n"
\t\t\t6.堆排序\n"
\t\t\t7.二路归并排序\n"
\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;
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:
shell_sort（s1）;
time2=（double）（finish-start）/CLOCKS_PER_SEC;
printf（"
希尔排序耗时%fseconds\n"
time2）;
case3:
bubble_sort（s1）;
time3=（double）（finish-start）/CLOCKS_PER_SEC;
冒泡排序耗时%fseconds\n"
time3）;
}
case4:
quick_sort（s1,1,NUM）;
time4=（double）（finish-start）/CLOCKS_PER_SEC;
快速排序耗时%fseconds\n"
time4）;
case5:
select_sort（s1）;
time5=（double）（finish-start）/CLOCKS_PER_SEC;
直接选择排序耗时%fseconds\n"
time5）;
case6:
heap_sort（s1）;
time6=（double）（finish-start）/CLOCKS_PER_SEC;
堆排序耗时%fseconds\n"
time6）;
case7:
merge_sort（s1）;
time7=（double）（finish-start）/CLOCKS_PER_SEC;
二路归并排序耗时%fseconds\n"
time7）;
case0:
{exit（0）;
}print_record（s1）;
}while（kk!
=0）;
}/*MAIN*/
4．测试结果
（1）选择直接插入排序：
排序前本有30000个随机数显示，但数据太多，只截一部分图来表示。
排序后也一样，应有30000个排好顺序的整数显示，但由于数据过多，也只截一部分图来表示。
由图可知，直接插入排序耗时0.878000秒
（2）选择希尔排序：
由图可知，希尔排序耗时0.026000秒
（3）选择冒泡排序：
由图可知，冒泡排序耗时3.456000秒
（4）选择快速排序：
由图可知，快速排序耗时0.005000秒
（5）选择直接选择排序：
由图可知，直接选择排序耗时1.528000秒
（6）选择堆排序：
由图可知，堆排序耗时0.008000秒
（7）选择二路归并排序：
由图可知，二路归并排序耗时0.006000秒
5.总结与体会
总结：
由上述比较我们可以清楚地知道，各种排序算法之间的差别是很大的。
其中在这几种不同的算法中，快速排序是其中最快的一种排序算法，其它几种算法都有些差异，其中冒泡排序最慢。
通过实验设计，我们可以明确感受一些内部排序方法选择的规则，其主要是
（1）当n较小时：
可采用直接插入排序和直接选择排序；
（2）当记录规模小时，可选择直接插入排序；
当记录规模大时，可选择直接选择排序，因为直接插入排序所需的记录移动操作比直接选择排序多；
（3）当记录基本有序时：
可采用直接插入排序和冒泡排序；
（4）当n较大时：
可采用快速排序和归并排序。
体会：
通过此次的课程设计，让我从中得到了许多锻炼，也学到了许多东西。
通过对排序算法的比较的设计，我更加深入地理解了算法的思想与原理，也深切地感受各种算法的运行时间长短，体会到它的优缺点，并且充分锻炼了我的动手能力，把理论与实践相结合，把学到的知识用于解决实际的问题。
而且，通过设计的操作，让我体会到了一个人力量的渺小，充分感受到了团队协作的力量，大家一起相互讨论，积极沟通，相互学习，相互帮助，锻炼了我的协作能力。
还有对于编程来说，让我体会到了看书很重要，但实在在动手去做才是硬道理，特别在调试的时候，要有足够的耐心与亲自不断尝试的能力，还有编程一定养成良好的编程习惯，无论命名还是结构。
尽管还有很多地方有待提高和改正，不管怎样通过此次的课程设计我受益匪浅，积累了经验，锻炼了自己分析问题、解决问题的能力。
6.参考文献
[1]秦锋、袁志祥.数据结构（C语言版）例题详解与课程设计指导.北京：
清华大学出版社
[2]XX文库
[3].严蔚敏，吴伟民，《数据结构（C语言版）》，清华大学出版社,2009
7.小组人员分工
组长：
韦志东
组员：
夏琪
分工：
韦志东：
主程序、随机函数生产、报告撰写
夏琪：
直接插入排序，希尔排序，冒泡排序，直接选择，，快速排序，堆排序，归并排序，数据记录。
升级会员 