实验八各种排序算法的实现
一．实验目的
掌握内部排序基本操作，即：直接插入排序、折半插入排序、快速排序、冒泡排序、希尔排序、堆排序、选择排序、基数排序等排序方法。
二、实验仪器
安装VC++的PC机。
三、实验原理
根据排序的思想编写算法并转化为程序实现其功能。
四、实验内容
输入待排序记录，分别用内部排序的几种排序方法对其排序。
参考程序如下：
#include
using namespace std;
#define Max 20
typedefstruct
{
int r[Max];
int length;
}Rectype;
Rectype Rec;
creat( )//生成带排序记录
{ int i=1;
cout<<"请输入待排序数据，输入数据为-1时结束！" <while(1)
{ scanf("%d",&Rec.r[i]);
if(Rec.r[i] ==-1 )break;
i++;
}
Rec.length=i-1;
}
//插入排序
voidinsertsort(int n)
{
inti,j;
for(i=2;i<=n;i++)
{
Rec.r[0]= Rec.r[i];
j=i-1;
while(Rec.r[0] {
Rec.r[j+1] = Rec.r[j];
j--;
}
Rec.r[j+1] = Rec.r[0] ;
}
}
//选择排序
voidselect_sort(int n)
{ intj,i,k,min,t;
for(i=0; i < n-1; i++)
{ j = i;
min = Rec.r[j];
for(k=i; k < n; k++)
{ if (Rec.r[k] < min) { j = k; min = Rec.r[k]; } }
t = Rec.r[i];
Rec.r[i] = Rec.r[j];
Rec.r[j] = t;
}
}
//冒泡排序
voidbubblesort(int n)
{
inti,j,noswap;
for(i=1;i<=n-1;j++)
{
noswap=1;
for(j=1;j<=n-i;j++)
if(Rec.r[j] >Rec.r[j+1])
{
Rec.r[0] = Rec.r[j];
Rec.r[j] = Rec.r[j+1];
Rec.r[j+1] = Rec.r[0];
noswap=0;
}
if(noswap)
break;
}
}
void print()//输出排序结果
int i;
cout<<"\n\n\n排序后:";
for(i=1;i<=Rec.length;i++)
printf("%3d", Rec.r[i]);
}
main()
{
int choice;
while(1)
{
cout<cout<<" ******************************\n\n";
cout<<" 1、输入待排序数据序列\n"; cout<<" 2、直接插入排序\n";
cout<<" 3、冒泡排序\n";
cout<<" 4、选择排序\n";
cout<<" 0、退出\n\n";
cout<<" ******************************\n\n";
cout<<"\n 输入你所选择的功能序号:";
cin>>choice;
switch(choice)
{
case 1: creat();
break;
case 2:insertsort(Rec.length);
print();
break;
case 3:select_sort(Rec.length);
print();
break;
case 4: bubblesort(Rec.length);
print();
break;
case 0: cout<<"\n 程序结束，按任意键返回！\n" ;
exit(0);
default: break;
}
}
五、实验步骤
1.预备知识的学习:了解各种排序的思想,存储方式.
2.上机前的准备：编写算法并将其数据类型和算法转换为对应的程序，并进行静态检查，
尽量减少语法错误和逻辑错误。
3.上机调试和测试程序。
4.实验报告在实验后要总结和整理实验报告
六、数据记录及处理
输入数据: 8 7 0 10 2 1
运行结果: 0 1 2 7 8 10
0 1 2 7 8 10
0 1 2 7 8 10
