七种排序算法的比较及每种排序的上机统计时间
《数据结构》课程
设计
领导形象设计圆作业设计ao工艺污水处理厂设计附属工程施工组织设计清扫机器人结构设计
报告
软件系统测试报告下载sgs报告如何下载关于路面塌陷情况报告535n,sgs报告怎么下载竣工报告下载
课题: 排序算法的比较
学院:信息学院
班级: 2011级电子信息
工程
路基工程安全技术交底工程项目施工成本控制工程量增项单年度零星工程技术标正投影法基本原理
1班
小组成员:韦志东(组长) 20111601310027
夏琪 20111601310028
完成时间: 2014-01-08
教师:周铁
目录
1、课程分析.......................................................... 2
1.1、选题 ..................................................................................................... 2
1.2、选题的意义及背景 .............................................................................. 2
1.3、设计任务
书
关于书的成语关于读书的排比句社区图书漂流公约怎么写关于读书的小报汉书pdf
„„„„„„„„„„„„„„„„„„„„„„„„2 2、设计分析.......................................................... 2
2.1、原始数据 ........................................................... 错误～未定义书签。2
2.2、输出数据 ........................................................... 错误～未定义书签。2
2.3、程序
流程
快递问题件怎么处理流程河南自建厂房流程下载关于规范招聘需求审批流程制作流程表下载邮件下载流程设计
图 ......................................................................................... 3
3、程序源代码及注释.................................................. 3 4、测试结果....................................... 错误～未定义书签。12 5、总结............................................................. 26 6、参考文献......................................................... 27 7、小组人员分工..................................................... 27
1
1、课程分析
1.1、选题要求
利用随机函数产生30000个随机整数，利用直接插入排序、希尔排序，冒泡排序、直接选择排序、快速排序、堆排序、归并排序的排序方法进行排序，并统计每一种排序上机所花费的时间。
1.2、选题的意义及背景
排序是计算机程序设计中的一种重要操作，它的功能是将一个数据元素的任意序列，重新排列成一个按关键词有序的序列。
此实验通过对各种内部排序算法进行比较，能使我们更好的掌握各种排序的基本思想，掌握各种排序方法的算法实现，掌握各种排序方法的优劣分析及花费的时间的计算，掌握各种排序方法所适应的不同场合。通过该题目的设计，可以加深理解各种数据结构的逻辑结构、存储结构及相应上运算的实现，进一步理解和熟练掌握课本中所学的各种数据结构，学会如何把学到的知识用于解决实际问题，培养我们的动手能力。
1.3、设计任务书
(1)定义结构体，头文件，定义数组范围，大小。
(2)依次描写七种排序的算法。
(3)描写产生随机函数的算法。
(4)描写菜单函数。
(5)描写主函数，调用七种排序的算法。
2、设计分析
2.1 原始资料
用户输入记录的个数30000个，数据由随机函数生成。
2.2 输出数据
产生的随机数分别用冒泡排序、直插排序、希尔排序、选择排序、快速排序、堆排序、归并排序这些排序方法进行排序，并统计每一种排序上机所花费的时间。
2
2.3 程序流程图
主程序
产生1组随机数
将随机数保存在数组中
二路
归并冒泡 直接
排序Shell 排序 直接堆排插入 快速选择序 排序 排序 排序 排序
输出排序上机所花费的时间
3(程序源代码及其注释
#include "stdio.h"
#include "stdlib.h"
#include "math.h"
#include
#include
#define MAX 60000 /*记录数组的个数*/
#define NUM 30000 /*实际输入数组的个数*/
3
typedef int datatype;
typedef struct /*定义记录为结构体类型*/
{ int key; /*记录的关键词域*/
datatype other; /*记录的其它域*/
} rectype;
rectype *s1,s[MAX];/*s[MAX]存放原始随机数，*s1取出原始数据后进行排序*/
/*直接插入排序算法如下*/
void insert_sort(rectype *r) /*对数组r按递增顺序进行插入排序算法*/
是一个常量*/ { int i,j,n=NUM; /*NUM为实际输入的记录数，
for(i=1;i<=n;i++) /* i0)
{ 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) /*记录交换*/
4
{ 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时终止本趟排序*/
jump=1且change=0时终止算法*/ }/*while*/ /*当增量
}/*SHELLSORT*/
/*冒泡排序算法如下*/
void bubble_sort(rectype *r) /*从下往上扫描的冒泡排序*/ { int i,j,noswap=0,n=NUM; /*noswap为交换标志,NUM为实际输入记录数*/ rectype temp;
for(i=1;i=i;j--) /*从下往上扫描*/
if(r[j].key=temp.key)&&(i0;i--)/*建立初始堆*/
shift(r,i,n);
for(i=n;i>1;i--)/*进行n-1趟筛选，交换，调整，完成堆排序*/
7
{ 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*/
/*二路归并排序算法如下*/
void merge(rectype *a,rectype *r,int low,int mid,int high)
{ int i,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++];
else r[k++]=a[j++];
}
while(i<=mid) r[k++]=a[i++];/*复制第一个有序子表的剩余记录*/ while(j<=high) r[k++]=a[j++];/*复制第二个有序子表的剩余记录*/ }/*MERGE*/
void merge_pass(rectype *r,rectype *r1,int length)
{ int i=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-17); return(kk);
}/*MENU_SELECT*/
main() /*算法比较--主程序模块*/
10
{
double time1, time2, time3, time4, time5, time6, time7;
clock_t start, finish;
int kk;
do {kk=menu_select(); /*进入主菜单选择模块*/
if(kk!=0) create(); /*建立记录数组*/
switch(kk)
{ case 1:{ start=clock();
insert_sort(s1);
finish=clock();
time1 = (double)(finish - start)/ CLOCKS_PER_SEC ;
printf( "直接插入排序耗时%f seconds\n", time1); break;}
case 2:{ start=clock();
shell_sort(s1);
finish=clock();
time2 = (double)(finish - start)/ CLOCKS_PER_SEC ;
printf( "希尔排序耗时%f seconds\n", time2); break;}
case 3:{ start=clock();
bubble_sort(s1);
finish=clock();
time3 = (double)(finish - start)/ CLOCKS_PER_SEC ;
printf( "冒泡排序耗时%f seconds\n", time3); break;}
case 4:{ start=clock();
quick_sort(s1,1,NUM);
finish=clock();
time4 = (double)(finish - start)/ CLOCKS_PER_SEC ;
printf( "快速排序耗时%f seconds\n", time4); break;}
case 5:{ start=clock();
select_sort(s1);
finish=clock();
11
time5 = (double)(finish - start)/ CLOCKS_PER_SEC ;
printf( "直接选择排序耗时%f seconds\n", time5); break;}
case 6:{ start=clock();
heap_sort(s1);
finish=clock();
time6 = (double)(finish - start)/ CLOCKS_PER_SEC ;
printf( "堆排序耗时%f seconds\n", time6); break;}
case 7:{ start=clock();
merge_sort(s1);
finish=clock();
time7 = (double)(finish - start)/ CLOCKS_PER_SEC ;
printf( "二路归并排序耗时%f seconds\n", time7); break;}
case 0:{ exit(0);}
}print_record(s1);
}while (kk!=0);
}/*MAIN*/
4(测试结果
12
(1)选择直接插入排序:
13
排序前本有30000个随机数显示，但数据太多，只截一部分图来表示。 排序后也一样，应有30000个排好顺序的整数显示，但由于数据过多，也只截一部分图来表示。
由图可知，直接插入排序耗时0.878000秒
14
(2)选择希尔排序:
排序前本有30000个随机数显示，但数据太多，只截一部分图来表示。 排序后也一样，应有30000个排好顺序的整数显示，但由于数据过多，也只截一部分图来表示。
由图可知，希尔排序耗时0.026000秒
15
16
(3)选择冒泡排序:
排序前本有30000个随机数显示，但数据太多，只截一部分图来表示。 排序后也一样，应有30000个排好顺序的整数显示，但由于数据过多，也只截一部分图来表示。
由图可知，冒泡排序耗时3.456000秒
17
18
(4)选择快速排序:
排序前本有30000个随机数显示，但数据太多，只截一部分图来表示。 排序后也一样，应有30000个排好顺序的整数显示，但由于数据过多，也只截一部分图来表示。
由图可知，快速排序耗时0.005000秒
19
20
(5)选择直接选择排序:
排序前本有30000个随机数显示，但数据太多，只截一部分图来表示。 排序后也一样，应有30000个排好顺序的整数显示，但由于数据过多，也只截一部分图来表示。
由图可知，直接选择排序耗时1.528000秒
21
22
选择堆排序: (6)
排序前本有30000个随机数显示，但数据太多，只截一部分图来表示。 排序后也一样，应有30000个排好顺序的整数显示，但由于数据过多，也只截一部分图来表示。
由图可知，堆排序耗时0.008000秒
23
24
选择二路归并排序: (7)
排序前本有30000个随机数显示，但数据太多，只截一部分图来表示。 排序后也一样，应有30000个排好顺序的整数显示，但由于数据过多，也只截一部分图来表示。
由图可知，二路归并排序耗时0.006000秒
25
26
与体会 5.总结
总结:由上述比较我们可以清楚地知道，各种排序算法之间的差别是很大的。其中在这几种不同的算法中，快速排序是其中最快的一种排序算法，其它几种算法都有些差异，其中冒泡排序最慢。
通过实验设计，我们可以明确感受一些内部排序方法选择的规则，其主要是(1)当n较小时:可采用直接插入排序和直接选择排序;(2)当记录规模小时，可选择直接插入排序;当记录规模大时，可选择直接选择排序，因为直接插入排序所需的记录移动操作比直接选择排序多;(3)当记录基本有序时:可采用直接插入排序和冒泡排序;(4)当n较大时:可采用快速排序和归并排序。 体会:通过此次的课程设计，让我从中得到了许多锻炼，也学到了许多东西。通过对排序算法的比较的设计，我更加深入地理解了算法的思想与原理，也深切地感受各种算法的运行时间长短，体会到它的优缺点，并且充分锻炼了我的动手能力，把理论与实践相结合，把学到的知识用于解决实际的问题。而且，通过设计
27
的操作，让我体会到了一个人力量的渺小，充分感受到了团队协作的力量，大家一起相互讨论，积极沟通，相互学习，相互帮助，锻炼了我的协作能力。还有对于编程来说，让我体会到了看书很重要，但实在在动手去做才是硬道理，特别在调试的时候，要有足够的耐心与亲自不断尝试的能力，还有编程一定养成良好的编程习惯，无论命名还是结构。尽管还有很多地方有待提高和改正，不管怎样通过此次的课程设计我受益匪浅，积累了经验，锻炼了自己分析问题、解决问题的能力。
6.参考文献
[1]秦锋、袁志祥.数据结构(C语言版)例题详解与课程设计指导.北京:清华大学出版社
[2]百度文库 www. Wenku.baidu,com
[3]. 严蔚敏，吴伟民， 《数据结构(C语言版)》，清华大学出版社,2009 7.小组人员分工
组长:韦志东
组员:夏琪
分工: 韦志东:主程序、随机函数生产、报告撰写
夏琪:直接插入排序，希尔排序，冒泡排序，直接选择，，快速排序，
堆排序，归并排序，数据记录。
28
浙公网安备 33021202002483