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

《实现冒泡排、直接插入排序和直接选择排序的算法.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

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

2、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()/*程序由此开始*/{inta[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]);/*输出排序后的序列*/}/*数据到此结束*/查看

3、程序是否正常运行。输入直接插入排序的运算程序：#defineN7voidsis(intr[],intn){inti,j;for(i=2;i<=n;i++)/*从第2个数开始逐个插入*/{r[0]=r[i];/*把待插数保存到r[0]中*/j=i-1;while(r[0]

4、;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]);/*程序到此结束*/}查看程序是否正常运行。输入直接选择排序的运算程序：#defineN6voidbustor(intx[],intn){inti,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

5、+1个数到n个数找最小数的下标k*/if(x[j]

6、排序结果*/printf("");/*程序到此结束*/}查看程序是否正常运行。五、程序验证：冒泡排序调试分析运行情况如下：9524（输入）2459（输出）直接插入排序调试分析;(1)运行结果如下：5894365（输入）3455689（输出）直接选择排序调试分析;(1)运行结果如下：582461（输入）124568（输出）25894（输入）24589（输出）冒泡排序：其时间复杂度为O（n2）其空间复杂度为O（1）直接插入排序：其时间复杂度为O（n）其空间复杂度为O（1）直接选择排序：其时间复杂度为O（n2）其空

7、间复杂度为O（1）六、问题及解决方法：冒泡排序：当运行此段程序发现运行结果与运行的用例应得的结果不同#defineN4voidbustor(intx[],intn)，{inti,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

8、=0;/*本趟发生数据交换*/}if(k==1)break;/*若第i趟未发生数据交换，则排序结束*/}}main()/*程序由此开始*/{inta[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]);