算法设计实验报告一..doc
文本预览下载声明
《计算机算法设计与分析》实 验 报 告
实验名称：排序算法效率比较 实验地点： 所使用的开发工具及环境： 实验目的：
比较至少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])
显示全部