直接插入排序、直接选择排序、堆排序、快速排序、冒泡排序的实验报告

学院专业：数字媒体技术班级：数媒091
姓名
学号
实验组
实验时间
指导教师
成绩
实验项目名称
实验目的
1．熟练掌握顺序表和有序表的查找方法。
2．熟悉静态查找树的构造方法和查找算法，熟练掌握二叉排序树的构造方法和查找算法。
3．掌握描述查找过程的判定树的构造方法，掌握各种查找方法在等概率情况下查找成功时的平均查找长度。
实验步骤
1、确定数据的结构
2、编写头文件、函数及变量声明
3、设计子函数
4、写主函数，并调用子函数
5、调试编写好的程序
6、编译正确后，运行，观察分析结果
实验内容
程序1内部排序算法比较
[问题描述]
编写常用的排序算法，并编写主程序测试。
[基本要求]
（1）对以下常用的6种排序算法进行比较：直接插入排序、直接选择排序、堆排序、快速排序、冒泡排序。
}
}
}
堆排序
void CreatHeap(ElemType A[], int n)
{
int i;
for( i = (n–2)/2; i >= 0; i--)
Sift(A, n, i); //调整A[i..n-1]使之为一个堆
}
void Sift(ElemType A[], int n, int i)
while ( i<=j ) {
while ( i<=j && A[i].stn <= x.stn ) i++; //从左到右
while ( i<=j && A[j].stn >= x.stn ) j--; //从右到左if ( i < j ) {
temp=A[i]; A[i]=A[j]; A[j]=temp;i++; j--;
ElemType x;
for ( i=0; i<=n-2; i++ )
{ //每一趟选择最小元素并与A[i]交换
k=i;
for (j=i+1; j<=n-1; j++) //查找最小元素的下标
if (A[j].stn <A[k].stn ) k=j;
if (k!=i) { //交换
x=A[i]; A[i]=A[k]; A[k]=x;
A[0] = A[i];
A[i] = x;
Sift(A, i, 0);//调整A[0..i-1]使之为一个堆
}
}
//冒泡排序
voidBubbleSort( ElemType A[],intn )
{
inti, j, flag;//flag为交换标记
ElemType x;
for(i=1; i<=n-1; i++) {//最多n-1趟排序
typedefintElemType;
//直接插入排序
voidInsertSort ( ElemType A[],intn )
{
inti, j;
ElemType x;
for( i=1; i<n; i++ ){//进行n-1次插入
x = A[i];//准备插入第i个元素
for( j=i-1; j>=0; j-- ){//从第i-1个开始往前找插入点
{
int i, j, flag; //flag为交换标记
ElemType x;
for (i=1; i<=n-1; i++) { //最多n-1趟排序
flag=0; //假设本次没有交换
for (j=n-1; j>=i; j--)//第i趟
if ( A[j].stn < A[j-1].stn ) {
flag=1; //出现交换
flag=0;//假设本次没有交换
for(j=n-1; j>=i; j--)//第i趟
if( A[j]< A[j-1]) {
flag=1;//出现交换
x=A[j]; A[j]=A[j-1]; A[j-1]=x;
}
if(flag==0)return;
}
}
//快速排序
voidQuickSort(ElemType A[],ints,intt)
InsertSort (A, N );
for(i=0;i<N;i++)
cout<<A[i]<<endl;
运//运行结果如右;
cout<<"直接选择排序:"<<endl;
SelectSort(A, N);
for(i=0;i<N;i++)
cout<<A[i]<<endl;
cout<<"堆排序:"<<endl;
HeapSort(A, N);
for(i=0;i<N;i++)
cout<<A[i]<<endl;
cout<<"冒泡排序:"<<endl;
BubbleSort(A, N);
for(i=0;i<N;i++)
cout<<A[i]<<endl;
cout<<"快速排序:"<<endl;
QuickSort(A,0,1);
{ //调整A[i..n-1]成为一个堆（它的左右子树已是一个堆）
ElemType x=A[i];
int j = 2 * i + 1; // j为i的左孩子
while (j <= n-1) { // i有左子树
if ( j +1 < n && A[j].stn < A[j+1].stn )
j++; //使j指向左右孩子中排序码大的孩子
for(i=0;i<N;i++)
cout<<A[i]<<endl;
}
实验总结
指导教师意见
签名：年月日
注：各学院可根据教学需要对以上栏木进行增减。表格内容可根据内容扩充。
k=i;
for(j=i+1; j<=n-1; j++)//查找最小元素的下标
if(A[j]<A[k]) k=j;
if(k!=i) {//交换
x=A[i]; A[i]=A[k]; A[k]=x;
}
}
}
//堆排序
voidSift(ElemType A[],intn,inti);
voidCreatHeap(ElemType A[],intn)
}
voidmain(){
inti,j,n,N=5;
cout<<"请输入个整数：";
ElemType A[5];
for(j=0;j<N;j++)
cin>>A[j];
cout<<"排序前为："<<endl;
for(i=0;i<N;i++)
cout<<A[i]<<endl;
cout<<"直接插入排序:"<<endl;
（2）待排序表的表长不小于100；其中的数据用自行设计。
（3）对结果作出分析。
直接插入排序
void InsertSort ( ElemType A[], int n )
{
int i, j;
ElemType x;
for ( i=1; i<n; i++ ) { //进行n-1次插入
x = A[i]; //准备插入第i个元素
实验要求
1．了解散列表的构造和查找算法。
2．了解各种排序方法的执行过程及其所依据的原则，掌握各种排序方法时间复杂度的分析方法。
3．熟练掌握希尔排序、快速排序、堆排序等高效排序算法。
实验原理
在visual c++编程环境中编写程序源代码，并编译、运行程序结果
实验仪器
奔腾2计算机或以上机型、visual c++编程环境
if( x< A[j] )
A[j+1]=A[j];
else
break;
}
A[j+1]=x;//插入
}
}
//直接选择排序
voidSelectSort(ElemType A[],intn)
{
inti, j, k;
ElemType x;
for( i=0; i<=n-2; i++ )
{//每一趟选择最小元素并与A[i]交换
{
inti;
for( i = (n-2)/2; i >= 0; i--)
Sift(A, n, i);//调整A[i..n-1]使之为一个堆
}
voidSift(ElemType A[],intn,inti)
{//调整A[i..n-1]成为一个堆（它的左右子树已是一个堆）
ElemType x=A[i];
x=A[j]; A[j]=A[j-1]; A[j-1]=x;
}
if (flag==0) return;
}
}
快速排序
void QuickSort(ElemType A[ ], int s, int t)
{ //递归算法，对区间A[s]～A[t]进行快速排序