- 1、本文档共6页,可阅读全部内容。
- 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
算法设计实验报告一
《计算机算法设计与分析》实 验 报 告
实验名称:排序算法效率比较 实验地点: 所使用的开发工具及环境: 实验目的:
比较至少4种排序算法的执行效率。已学过的算法:起泡排序、选择排序、插入排序、shell排序,归并排序、快速排序等。
二、实验内容:
1、从中选择至少4中排序算法,写成独立的函数进行调用。
2、参与排序的数据不少于10000个,要求用数据文件存储随机产生的数据。
3、要求在main()函数中调用以上函数,并输出各排序算法所用时间。 基本思想、原理和算法描述:
本次实验要求写出四种算法,来比较它们运行的时间。
冒泡排序:
总的时间复杂度为O(n).
基本思想:首先将第一个记录的关键字和第二个记录的关键字进行比较,若为逆序,则将两个记录交换,然后比较第二个记录和第三个记录的关键字。依此类推,直到第n-1和第n个的关键字进行比较为止。
算法描述:
void BubbleSort(int r[],int length) //冒泡排序
{
int i,j,temp;
for(j=length;j0;j--)
for(i=0;ij-1;i++)
if(r[i]r[i+1])
{
temp=r[i];
r[i]=r[i+1];
r[i+1]=temp;
}
}
简单选择排序:总的时间复杂度为O()
基本思想:通过n-i次关键字的比较,从n-i+1个记录中选取出关键字最小的记录并和第i个记录交换。
算法描述:
void SelectSort(int r[],int length) //简单选择排序
{
int i,j,k;
int x;
for (i=1;i=length-1;++i)
{
k=i;
for(j=i+1;j=length;++j)
if(r[j]r[k])
k=j;
if( k!=i)
{
x= r[i];
r[i]=r[k];
r[k]=x;
}
}
}
插入排序:总的时间复杂度为:O()
算法描述:
void InsertSort(int r[],int length) //插入排序
{
int i,j;
for (i=0;i=length;i++)
{
r[0]=r[i];
j=i-1;
while(r[0]r[j])
{
r[j+1]=r[j];
j=j-1;
}
r[j+1]=r[0];
}
}
快速排序:总的时间复杂度为O()
基本思想:通过一趟排序将待排记录分割成独立的两部分,其中一部分的关键字均比另一部分的关键字小,则可分别对这两部分的记录继续进行排序,直到整个序列有序。
算法描述:
void QuickSort(int A[],int low,int r) //快速排序
{
if(lowr)
{
int high = Partition(A,low,r);
QuickSort(A,low,high-1);
QuickSort(A,high+1,r);
}
} 源程序清单:
#includestdio.h
#includestdlib.h
#includetime.h
#includewindows.h
#define MAX 10000
void BubbleSort(int r[],int length) //冒泡排序
{
int i,j,temp;
for(j=length;j0;j--)
for(i=0;ij-1;i++)
if(r[i]r[i+1])
{
temp=r[i];
r[i]=r[i+1];
r[i+1]=temp;
}
}
void SelectSort(int r[],int length) //简单选择排序
{
int i,j,k;
int x;
for (i=1;i=length-1;++i)
{
k=i;
for(j=i+1;j=length;++j)
if(r[j]r[k])
k=j;
if( k!=i)
{
x= r[i];
r[i]=r[k];
r[k]=x;
}
}
}
void InsertSort(int r[],int length) //插入排序
{
int i,j;
for (i=0;i=length;i++)
{
r[0]=r[i];
j=i-1;
while(r[0]r[j])
文档评论(0)