《数据结构》上机实验报告—常用排序算法的实现.pdf

福州大学数计学院
《数据结构》上机实验报告

专业和班级：信息计算科学与应用数学6班
学号姓名成绩
实验名称排序实验实验内容常用排序算法的实现
【实验目的】
熟悉并掌握各种排序算法的思想方法和实现该算法的基本技术
【实验内容】
实从键盘输入一组关键字序列分别实现下列排序:
验1.实现简单选择排序、直接插入排序和冒泡排序。
目2.实现快速排序算法。
的3.实现折半插入排序。
和4.采用几组不同数据测试各个排序算法的性能（比较次数和移
要动次数）。
求【实验要点及说明】
在主函数中设计一个简单的菜单，分别测试上述算法，
最后要在屏幕上输出排序后的记录。
主要程序：

#include<iostream.h>

#include<stdlib.h>
#defineOK1
#defineERROR0

#defineOVERFLOW-1
问
constintMAXSIZE=30;//顺序表的最大长度
题
描typedefstruct
述{
和intkey;//关键字项
主intdata;
要}record;//记录类型
步typedefstruct
骤{

recordr[MAXSIZE+1];
intlength;//顺序表长度
}Form;//顺序表类型
intInit_Form(Form&F)
{
inti;
for(i=0;i<=F.length;i++)
F.r[1].key=F.r[i].data=0;
returnOK;
}

intprint(Form&F,intcomp,intmove)
{
inti;
关键字数据项
for(i=1;i<=F.length;i++)

比较次数为：
移动次数为：
returnOK;
}

intInsertSort(Form&F)
{//对顺序表F作直接插入排序
inti,j;
intcomp=0;//比较次数
intmove=0;//移动次数
for(i=2;i<=F.length;i++)
{
comp++;
if(F.r[i].key<F.r[i-1].key)
{
F.r[0]=F.r[i];//F.r[0]是监视哨
F.r[i]=F.r[i-1];
j=i-2;
comp++;
if(F.r[0].key<F.r[j].key)
{//进行元素移动，以腾出位置插入F.r[i]
F.r[j+1]=F.r[j];//记录后移
j--;
move++;
}
F.r[j+1]=F.r[0];//在j+1处插入F.r[i]
}
}
直接插入排序的结果为：
print(F,comp,move);
returnOK;
}

intPartition(Form&F,intlow,inthigh);
intQuickSort(Form&F,intlow,inthigh)
{//快速排序法

intcomp=0;
intmove=0;
if(low<high)
{
comp++;
intp=Partition(F,low,high);
QuickSort(F,low,p-1);
QuickSort(F,p+1,high);
}
快速排序的结果为：
print(F,comp,move);
returnOK;
}
intPartition(Form&F,intlow,inthigh)
{
intcomp=0;
intmove=0;
F.r[0]=F.r[low];
intp=F.r[low].key;
while(low<high)
{
comp++;
if(low<high&&F.r[high].key>=p)
{
high--;
move++;
}
F.r[low]=F.r[high];
if(low<high&&F.r[low].key<=p)
{
low++;
move++;
}
F.r[high]=F.r[low];
}
F.r[low]=F.r[0];
returnlow;
}

voidmain()
{
FormF;

Init_Form(F);
intn;
请输入顺序表的长度
cin>>n;
F.length=n;
请输入数据
for(inti=1;i<F.length+1;i++)
cin>>F.r[i].key>>F.r[i].data;
intlow;
inthigh;
InsertSort(F);
QuickSort(F,low,high);
}
结果截图：

研
究
与
探
讨
说明：实验名称为教学大纲中各章的实验项目名称，实验内容为具体章节的实
验内容名称