排序算法分析
- 格式：doc
- 大小：335.50 KB
- 文档页数：15
实 验 报 告
课程名称 计算机软件基础
实验项目 排序算法分析
实验仪器 VS2005
系 别__ 光电信息与通信工程
专 业__ __电子信息工程
班级/学号_ _
学生姓名 __ ___________
实验日期 _______________________
成 绩 _______________________
指导教师 _______________________
实验五、排序算法分析
1、实验目的：
掌握顺序表的常用排序方法，掌握算法性能测算技术。通过实验测算各排序算法的性能并进行分析比较。
2、 实验内容：
1) 分别编写函数实现插入排序、冒泡排序和快速排序算法，算法应具有记录比较次数和移动次数的功能，以及显示每趟排序中间结果的功能。
2) 编制一个应用程序，它将随机产生的n个整数插入到一个顺序表中，然后分别用上述排序算法对这个顺序表进行排序，并显示各种方法的比较次数和移动次数；
3) 取n=10，运行程序，检察排序中间结果及次数统计是否正确。
选做内容：
4) 修改程序，关闭算法输出中间结果的功能，然后分别以n=50、500和5000运行这个程序，对次数的统计结果作出分析和解释。
5) 利用计时函数实现对排序算法的运行时间计时。
6) 分析说明：影响排序时间、比较次数及交换次数的因素有哪些？
3、实验步骤 （1）插入排序：
运行结果：
(2)冒泡排序：
运行结果：
(3)快速排序：
运行结果:
(4)比较次数统计与分析
n=50
n=500
n=5000
通过比较可以看出，快速排序效率最高，而且排序数列越多越能显示其效率，冒泡排序和插入排序移动次数相差不大，但是比较次数相差相当大，所以平均来说，冒泡排序的时间复杂度最高，插入排序时间复杂度居中，快速排序最小。
下面的截图更能说明这一点：
由图中我们可以发现，快速排序所花时间最少，插入排序次之，冒泡排序最慢。
影响排序时间、比较次数和移动次数的主要因素有待排序的数据记录数目、序列的初始状态等等。
4、程序清单
#include
#include
#include
#define M 5000 //M为待排序记录的最大数目
struct record {
int key;
int otheritem;
};
typedef struct record RECORD;
long comp; //比较次数
long move; //移动次数
void printfile(RECORD R[],int n) //输出数列
{
int i;
for (i=0;i
{
if(R[i].key<10)printf(" ");
printf(" %d",R[i].key);
}
printf("\n");
}
void insertsort(RECORD R[],int n) //插入排序 { int i, j;
RECORD temp;
for(i=1;i
temp=R[i];
j=i-1;
comp++;
while(temp.key=0){
R[j+1]=R[j];
move++;
comp++;
j--;
}
R[j+1]=temp;
move+=2;
printfile(R,n); //显示中间排序结果
}
}
void bubblesort(RECORD R[], int n)
//修改算法,加入比较次数和移动次数统计,以及显示中间排序结果
{
int i,j,flag; RECORD temp;
i=1;
flag=1;
while(flag)
{
flag=0;
for(j=0;j
{
comp++; //比较次数统计
if(R[j].key>R[j+1].key)
{
temp=R[j];
R[j]=R[j+1];
R[j+1]=temp;
flag=1;
move++; //移动次数统计
printfile(R,n); //显示中间排序结果
}
}
i++;
} }
int qpass(RECORD R[],int n, int low, int high)
//修改算法,加入比较次数和移动次数统计
{
int i, j, k;
RECORD x;
i=low;
j=high;
x=R[low];
k=x.key;
while(i
while((i=k))
{
j--;
comp++; //比较次数
}
R[i]=R[j];
move++; //移动次数
printfile(R,n); //显示中间排序结果
while((i
{ i++;
comp++; //比较次数
}
R[j]=R[i];
move++; //移动次数
printfile(R,n); //显示中间排序结果
}
R[i]=x;
return(i);
}
void quicksort(RECORD R[], int n, int low, int high)//快速排序
{
int i;
if (low
{
i=qpass(R,n,low,high);
quicksort(R,n,low,i-1); //递归调用
quicksort(R,n,i+1,high); //递归调用
}
}
void main()
{
RECORD file[M],file1[M],file2[M];
int i,n;
clock_t start,end; //记录起始时间和结束时间
double duration; //记录排序时间
printf("输入记录个数: ");
scanf("%d", &n);
//产生待排序文件
srand((unsigned)time(NULL));
for (i=0; i
{
file[i].key=rand()%100;
file1[i]=file[i];
file2[i]=file[i];
}
printf("原始数据: \n");
printfile(file,n);
comp=0; move=0;
printf("插入排队过程:\n"); //printfile(file,n);
start=clock(); //插入排序起始时间
insertsort(file,n);
end=clock(); //插入排序结束时间
duration=(double)(end-start); //插入排序时间
//显示统计结果
printf("比较次数：%d\n" ,comp);
printf("移动次数：%d\n",move);
printf("时间：%.2f\n\n",duration); //输出插入排序时间
comp=0; move=0;
printf("冒泡排队过程:\n");
printfile(file1,n);
start=clock(); //冒泡排序起始时间
bubblesort(file1,n);
end=clock(); //冒泡排序结束时间
duration=(double)(end-start); //冒泡排序时间
//显示统计结果
printf("比较次数：%d\n" ,comp);
printf("移动次数：%d\n",move);
printf("时间：%.2f\n\n",duration);//输出冒泡排序时间
comp=0; move=0;
printf("快速排队过程:\n");
printfile(file2,n);
start=clock(); //快速排序起始时间
quicksort(file2,n,0,n-1);
end=clock(); //快速排序结束时间
duration=(double)(end-start); //快速排序时间
//显示统计结果
printf("比较次数：%d\n" ,comp);
printf("移动次数：%d\n",move);
printf("时间：%.2f\n",duration); //输出快速排序时间
}
5、总结
这次实验，我学会了三种排序方法，了解了它们的区别，也发现了各种排序算法的适用场合：1)当待排序数目较小时，直接插入排序较好；
2)当待排序数据的初始状态基本有序(指正序)，则应选用插人排序或冒泡排序；
3)若待排序数目较大，则应选择快速排序。
实验过程中出现过很多错误，主要是对排序算法的思想理解不清，在
