实现冒泡排序、直接插入排序和直接选择排序的算法.doc

实验报告

一、实验题目：冒泡排序、直接插入排序和直接选择排序的算法。
二、实验环境：window7、mytc、计算机一台
三、实验目的：通过编程熟练掌握实现冒泡排序、直接插入排序和直接选择排序的算法。
四、实验内容：（1）输入数据运算字符。
首先输入冒泡排序的运算程序：
#define N 4
void bustor(int x[], int n)
{
int i,j,m,k;
for(i=1;i<=n-1;i++) /*n个数进行n-1趟排序*/
{
k=1; /*各趟开始假定本趟不会发生数据交换*/
for(j=1;j<=n-1;j++) /*第i趟比较n-i次*/
if(x[j]>x[j+1])
{
m=x[j];
x[j]=x[j+1]; /*相邻两数交换*/
x[j+1]=m;
k=0; /*本趟发生了数据交换*/
}
if(k==1)break;
}
}

之后运行主程序
main() /*程序由此开始*/
{
int a[N+1],i;
for(i=1;i<=N;i++)
scanf("%d",&a[i]); /*输入N个数*/
bustor(a,N); /*调用冒泡排序函数*/
for(i=1;i<=N;i++)
printf("%4d",a[i]); /*输出排序后的序列*/
} /*数据到此结束*/
查看程序是否正常运行。

输入直接插入排序的运算程序：
#define N 7
void sis(int r[], int n)
{
int i,j;
for(i=2;i<=n;i++) /*从第2个数开始逐个插入*/
{
r[0]=r[i]; /*把待插数保存到r[0]中*/
j=i-1;
while(r[0]<r[j]) /*待插数小于前面数时，做下面工作*/
{
r[j+1]=r[j]; /*前面数据后移1位*/
j--;
}
r[j+1]=r[0]; /*找到了插入位置，第i个数插入完毕*/
}
}

之后运行主程序
main() /*程序由此开始*/
{
int a[N+1],i;
for(i=1;i<=N;i++)
scanf("%d",&a[i]); /*输入n个数*/
sis(a,N); /*输入n个数*/
for(i=1;i<=N;i++)
printf("%4d",a[i]); /*程序到此结束*/
}
查看程序是否正常运行。

输入直接选择排序的运算程序：
#define N 6
void bustor(int x[], int n)
{
int i,j,m,k;
for(i=1;i<=n-1;i++) /*n个数进行n-1趟排序*/
{
k=i; /*第i趟开始假设第i个数最小*/
for(j=i+1;j<=n;j++) /*从第i+1个数到n个数找最小数的下标k*/
if(x[j]<x[k])
k=j;
if(k!=i) /*若最小数不在第i个位置，则交换*/
{
m=x[i];
x[i]=x[k];
x[k]=m;
}
}
}
/*返回main中sestor（a，N）；的下一句*/
之后运行主程序
main() /*程序由此开始*/
{
int a[N+1],i;
for(i=1;i<=N;i++)
scanf("%d",&a[i]); /*输入N个数*/
bustor(a,N); /*调用排序函数*/
for(i=1;i<=N;i++)
printf("%4d",a[i]); /*输出排序结果*/
printf("\n"); /*程序到此结束*/
}

查看程序是否正常运行。
五、程序验证：
冒泡排序调试分析
运行情况如下：
9 5 2 4 （输入）
2 4 5 9 （输出）
直接插入排序调试分析;
(1)运行结果如下：
5 8 9 4 3 6 5 （输入）
3 4 5 5 6 8 9 （输出）
直接选择排序调试分析;
(1)运行结果如下：
5 8 2 4 6 1 （输入）
1 2 4 5 6 8 （输出）
2 5 8 9 4 （输入）
2 4 5 8 9 （输出）
冒泡排序：
其时间复杂度为O（n2）
其空间复杂度为O（1）
直接插入排序：
其时间复杂度为O（n）
其空间复杂度为O（1）
直接选择排序：
其时间复杂度为O（n2）
其空间复杂度为O（1）

六、问题及解决方法：
冒泡排序：
当运行此段程序发现运行结果与运行的用例应得的结果不同
#define N 4
void bustor(int x[], int n)，
{
int i,j,m,k;
for(i=1;i<=n-1;i++) /*n个数进行n-1趟排序*/
{
k=1; /*各趟开始假定本趟不会发生数据交换*/
for(j=1，j<=n-1，j++) /*第i趟比较n-i次*/
if(x[j]>x[j+1]) /*若前面的数大于后面的数则交换*/
{
m=x[j];
x[j]=x[j+1]; /*相邻两数交换*/
x[j+1]=m;
k=0; /*本趟发生数据交换*/
}
if(k==1)break; /*若第i趟未发生数据交换，则排序结束*/
}
}
main() /*程序由此开始*/
{
int a[N+1],i;
for(i=1;i<=N;i++)
scanf("%d",&a[i]); /*输入N个数*/
bustor(a,N); /*调入冒泡排序函数*/
for(i=1;i<=N;i++)
printf("%4d",&a[i]); /*输入排序后的序列*/
} /*程序到此结束*/
经检查发现void bustor(int x[], int n)，语句加了，导致程序运行错误。
for(j=1，j<=n-1，j++)语句中应该是；导致程序运行错误
直接插入排序：
当运行此段程序发现运行结果与运行的用例应得的结果不同

#define N 7
void sis(int r[], int n)
{
int i,j;
for(i=2;i<=n;i++) /*从第2个数开始逐个插入*/
{
r[0]=r[i]; /*把待插数保存到r[0]中*/
j=i-1;
while(r[0]<r[j]) /*待插数小于前面数时，做下面工作*/
{
r[j+1]=r[j]; /*前面数据后移1位*/
j--;
}
r[j+1]=r[0]; /*找到了插入位置，第i个数插入完毕*/
}
}
main() /*程序由此开始*/
{
int a[N+1],i;
for(i=1;i<=N;i++)
scanf("%d",a[i]); /*输入n个数*/
sis(a,N); /*输入n个数*/
for(i=1;i<=N;i++)
printf("%4d",a[i]); /*程序到此结束*/
}
经检验发现scanf("%d",&a[i]);

scanf("%d",a[i]); 语句没有地址符，导致程序运行错误，并且发现mytc在window7系统中总出错，也不知是什么原因。
直接选择排序：
当运行此段程序发现运行结果与运行的用例应得的结果不同
#define N 6
void bustor(int x[], int n)
{
int i,j,m,k;
for(i=1;i<=n-1;i++) /*n个数进行n-1趟排序*/
{
k=i; /*第i趟开始假设第i个数最小*/
for(j=i+1;j<=n;j++) /*从第i+1个数到n个数找最小数的下标k*/
if(x[j]<x[k])
k=j;
if(k!=i) /*若最小数不在第i个位置，则交换*/
{
m=x[i];
x[i]=x[k];
x[k]=m;
}
}
} /*返回main中sestor（a，N）；的下一句*/
main() /*程序由此开始*/
{
int a[N+1],i;
for(i=1;i<=N;i++)；
scanf("%d",&a[i]); /*输入N个数*/
bustor(a,N); /*调用排序函数*/
for(i=1;i<=N;i++)
printf("%4d",a[i]); /*输出排序结果*/
printf("\n"); /*程序到此结束*/
}
经检验发现bustor(a,N);调用排序函数忘记了，导致程序运行错误。并且for(i=1;i<=N;i++)添加；导致程序运行错误。
在以上的种种的失误中，我觉得归根到底还是自己的基本知识没有掌握好，有些知识点以为学会了，其实在实际的操作中不断检验出自己有这样或那样的不足之处。而这次操作让我也有了不小的收获。

实验人员
姓名：张坤 学号：031210500148 学校：淄博职业学院