计算机软件基础实验报告3.docVIP

PAGE1

北京联合大学

实验报告

课程（项目）名称：计算机软件技术基础（实验3）

学院：自动化专业：电气工程与自动化

班级：0910030101成绩：

学号：2009100301126姓名：林驷淇

2011年

一、任务与目的

1．实验目的

（1）掌握直接插入排序的算法。

（2）掌握冒泡排序的算法。

（3）掌握简单选择排序的算法。

（4）掌握快速排序的算法。

2.实验内容

编写算法，利用直接插入排序的算法、冒泡排序的算法、简单选择排序的算法（快速排序与堆排序自选）对数据序列进行排序（大于20000个数据，可用随机函数产生数据）。测试要求：在原始数据随机、正序和逆序情况下，进行排序效率的比较，给出结果（排序使用的时间表）

二、原理（条件）

VisualC++6.0

三、内容与步骤

1.直接插入排序算法

实现代码：

voidinsertSort(rectypeR[])//插入排序

{ inti,j;

for(i=2;i<=size;i++)

{

R[0]=R[i];

j=i-1;

while(R[0].key<R[j].key)

{

R[j+1]=R[j];

j--;

}

R[j+1]=R[0];

}

}

运行结果：

正序排序和插入法比较

逆序排序和插入法比较

2.冒泡排序算法

实现代码：

voidpopoSort(rectypeR[])//冒泡法

{

inti,j;

intflag=0;

rectypetemp;

for(i=1;i<size-1;i++)

{

flag=0;

for(j=1;j<size-i;j++)

if(R[j].key>R[j+1].key)

{flag=1;

temp=R[j];R[j]=R[j+1];R[j+1]=temp;}

if(flag==0)break;

}

}

运行结果：

正序排序和冒泡法比较

逆序排序和冒泡法比较

3.简单选择排序的算法

实现代码：

正序排列：

voidselectSort(rectypeR[])//正序排列

{

inti,j,k;

rectypetemp;

for(i=1;i<size;i++)

{

k=i;

for(j=i+1;j<size;j++)

if(R[j].key<R[k].key)k=j;

if(i!=k)

{

temp=R[i];R[i]=R[k];R[k]=temp;

}

}

}

逆序排列：

voidselectSort2(rectypeR[])//逆序排列

{

inti,j,k;

rectypetemp;

for(i=1;i<size;i++)

{

k=i;

for(j=i+1;j<size;j++)

if(R[j].key>R[k].key)k=j;

if(i!=k)

{

temp=R[i];R[i]=R[k];R[k]=temp;

}

}

}

运行结果：

正序排列

逆序排列

4.掌握快速排序的算法

实现代码：

intPartition(rectypeR[],intl,inth)//返回划分后被定位的基准记录的位置

/*对无序区R[l]～R[h]做划分*/

{

inti,j;

rectypetemp;

i=l;j=h;temp=R[i];

do

{

while((R[j].key>=temp.key)&&(i<j))

j--;/*从右向左扫描，查找第一个关键字小于temp.key的记录*/

if(i<j)

R[i++]=R[j]; /*交换R[i]和R[j]*/

while((R[i].key<=temp.key)&&(i<j))

i++;/*从左向右扫描，查找第一个关键字大于temp.key的记录*/

if(i<j)

R[j--]=R[i]; /*交换R[i]和R[j]*/

}while(i!=j);

R[i]=temp; /*基准temp已被最后定位*/

returni;

}

voidquickSort(rectypeR[],intlow,inthigh)//快速排序

{

inti;

if(low<high)