实验九 选择排序和插入
- 格式：doc
- 大小：55.00 KB
- 文档页数：5
实验九选择排序和插入排序
一、实验要求
1、实验前，务必预习实验内容，深入了解相关知识，先人工分析程序并写出分析结果，然后上机运行、调试程序，得出最终正确结果；
2、实验中，认真思考所做的每一步，弄懂其中的道理，填写好实验过程；
3、实验后，总结经验教训，写出实验体会和收获，为今后学习奠定良好的基础。
二、实验目的
1、掌握排序的相关概念；
2、复习堆排序的算法；
3、掌握简单选择排序的算法；
4、掌握直接插入排序、折半插入排序、希尔排序的算法；
三、实验学时：2学时。
四、实验内容
1、已知排序码序列（704, 84,532,926,61,408，28,167）为例，演示下面
的排序算法(递增)，写出前三趟结束时的排序码状态。
（1）简单选择排序；
第一趟结束时的排序码状态：[28] [84 532 926 61 408 704 167]
第二趟结束时的排序码状态：[28 61] [532 926 84 408 704 167]
第三趟结束时的排序码状态：[28 61 84] [926 532 408 704 167] （2）堆排序；
第一趟结束时的排序码状态：926 704 532 167 61 408 28 84
第二趟结束时的排序码状态：704 167 532 84 61 408 28 926
第三趟结束时的排序码状态：167 84 532 28 61 408 704 926（3）直接插入排序；
第一趟结束时的排序码状态:84 [84 704] [532 926 61 408 28 167]
第二趟结束时的排序码状态:532 [84 532 704] [926 61 408 28 167]
第三趟结束时的排序码状态:61 [61 84 532 704] [926 408 28 167]（4）希尔排序；（排序增量为4、2、1）
排序增量为4的排序码状态：61 84 28 167 704 408 532 926
排序增量为2的排序码状态：28 84 61 167 532 408 704 926
第三趟结束时的排序码状态：28 61 84 167 408 532 704 926 2、编写主函数main，调用排序算法并测试排序结果。
源程序如下：
#include "stdio.h"
typedef double ElemType;
void InsertSort(ElemType a[],int n)
{
int i,j;
for(i=2;i<=n;i++)
{
a[0]=a[i];
j=i-1;
while(a[0]<a[j])
{
a[j+1]=a[j];
j--;
}
a[j+1]=a[0];
}
}
void BinSort(ElemType a[],int n)
{
int i,j,Low,High,Middle;
for(i=2;i<=n;i++)
{
a[0]=a[i];
Low=1;High=i-1;
while(Low<=High)
{
Middle=(Low+High)/2;
if(a[0]<a[Middle])
High=Middle-1;
else
Low=Middle+1;
}
for(j=i-1;j>=High+1;j--)
a[j+1]=a[j];
a[High+1]=a[0];
}
}
void ShellSort(ElemType a[],int n)
{
int i,j,d;
for(d=n/2;d>=1;d=d/2)
{
for(i=1+d;i<=n;i++)
{
a[0]=a[i];
j=i-d;
while(j>0&&a[0]<a[j])
{
a[j+d]=a[j];
j=j-d;
}
a[j+d]=a[0];
}
}
}
void main()
{
ElemType a[]={9999,704,84,532,926,61,408,28,167};
int i;
int n=8;
InsertSort(a,n);
printf("直接插入排序的结果是：");
for(i=1;i<=n;i++)
printf(" %.f",a[i]);
printf("\n");
BinSort(a,n);
printf("折半插入排序的结果是：");
for(i=1;i<=n;i++)
printf(" %.f",a[i]);
printf("\n");
ShellSort(a,n);
printf("希尔排序的结果是： ");
for(i=1;i<=n;i++)
printf(" %.f",a[i]);
printf("\n");
}
运行结果如下：
五、实验过程中存在的问题及解决方法
1．出现的问题：定义ElemType是double型，而在最后输出的时候误用“%d”
输出，导致输出结果有误。
解决办法：将输出的类型改为“%.f”即可。
2．出现的问题：在运行的时候，多输入一个数据。
解决办法：输出时的for循环的次数多一次，将“n=0;”改为“n=1;”即可。
六、实验体会和收获
通过本次实验，我对简单选择排序和各插入排序有了清楚的认识，在之前对各种算法不是很明确，分不清楚各自的优缺点。
但通过这次实验，我知道插入排
序有直接插入排序、折半插入排序和希尔排序三种。
这次实验的编写插入排序的算法将插入排序的三种算法放在一起，可以起到比较作用，虽然三者的运行结果一样，但效率却有很大的区别。
直接插入排序和折半插入排序是稳定的排序算法，而简单选择排序和希尔排序是不稳定的排序算法。
在一开始写各排序算法的前三趟排序结束时的情况的时候，由于对各算法的认识不明确，导致不能正确的写出结果。
不过，在复习了一遍书上的内容，分清了各排序算法的思想。
但是对堆排序还是不是很清楚的理解，仍有点不懂，因而只能模仿书上的小根堆的排序思想建立大根堆，并进行排序，写出结果。
但这次实验让我对堆排序的思想有了更多的认识，知道了建立小根堆排序的结果是降序的，而大根堆的排序结果才是增序的。
