算法设计实验报告一_
- 格式：pdf
- 大小：420.27 KB
- 文档页数：8
算法设计实验报告
一、实验内容：
题目：题目：11、
编程实现常见排序算法，如插入排序、归并排序、快速排序、随机化的快速排
序等，并统计不同输入规模下（序等，并统计不同输入规模下（11组从小到大排序，组从小到大排序，11组从大到小排序，其余组从大到小排序，其余88组随机）的平均物理执行时间。
2、
编程实现循环赛日程表
设有设有n=2kn=2kn=2k个运动员要进行网球循环赛，先要设计一个满足一下要求的比赛日常表：个运动员要进行网球循环赛，先要设计一个满足一下要求的比赛日常表：
（1）每个选手必须与其他）每个选手必须与其他n-1n-1n-1个选手各赛一次个选手各赛一次
（2）每个选手一天只能赛一次
（3）循环赛一共进行n-1天
二、核心代码说明：
1、 sort.h
template
struct SqList{
type * key;
int length;
};
template
void CreateSqList(SqList &> &slsl)//type为int
{
int n;
cout<
请输入顺序表的长度"<
cin>>n;
sl.length=n;
sl.key=.key=newnew
int[sl.length+1];
assert(sl.key);
srand(time(0));
for(int i=1;i<=sl.length;i++)
{
sl.key[i]=rand();
}
}
template
void OutPut(SqList &> &LL)
{
for(int j=1;j<=L.length;++j)
cout<
cout<
}
//折半插入排序
template void BInsertSort(SqList &> &LL)
{
int high,low,m; for(int i=2;i<=L.length;i++)
{
L.key[0]=.key[0]=LL.key[i];.key[i];////
将L.key[i]
暂存到L.key[0]
low=1;
high=i-1;
while(low<=high)(low<=high)////
在key[low]
到key[high]
中折半查找有序插
入的位置
{
m=(low+high)/2;m=(low+high)/2;////
折半
if(L.key[0]<=.key[0]<=LL.key[m])
high=m-1;high=m-1;////
插入低半区
else
low=m+1;low=m+1;////
插入高半区
}
for(int j=i-1;j>=high+1;--j)
L.key[j+1]=.key[j+1]=LL.key[j]; //
记录后移
L.key[high+1]=.key[high+1]=LL.key[0]; //
插入
}
}
//归并排序
template
void Merge(type * *SRSR,type * *TRTR,int i,int
m,int
n)
{//将有序的SR[i...m]
和SR[m+1...n]
归并为有序的TR[i...n]
int j,k;
for(j=(j=mm+1,k=+1,k=ii;i<=<=mm&&j<=&&j<=nn;k++);k++)////
将SR
中的记录由大到小并入TR
{
if(SR[i]<=]<=SRSR[j])
TR[k]=[k]=SRSR[i++];
else
TR[k]=[k]=SRSR[j++];
}
if(i<=<=mm)//
将剩余的SR[i...m]
赋值到TR
for(int a= a=ii;a<=;a<=mm;a++)
TR[k++]=[k++]=SRSR[a];
else
if(j<=(j<=nn)//
将剩余的SR[j...n]
复制到TR
for(int b=j;b<=n;b++)
TR[k++]=[k++]=SRSR[b];
}
template
void MSort(type * *SRSR,type * *TR1TR1,int s,int
t)
{
type TR2[100000];//
数组大小可以根据实际情况重新定义
int m;
//
将SR[s...t]
归并排序为TR[s...t]
if(s====tt)
TR1[s]=]=SRSR[s];
else
{
m=(m=(ss+t)/2;)/2;////
将SR[s...t]
平分为SR[s...m]和SR[m+1...t]
MSort(MSort(SRSR,TR2,,TR2,ss,m);,m);////
递归地将SR[s...m]归并为有序的
TR2[s...m]
MSort(MSort(SRSR,TR2,m+1,,TR2,m+1,tt););////
递归地将SR[m+1...t]归并为
TR2[m+1...t]
Merge(TR2,Merge(TR2,TR1TR1,s,m,,m,tt););////
将TR2[s...m]和TR2[m+1...t]
归并
到TR1[s...t]
}
}
template
void MergeSort(SqList &L)
{//对顺序表L
作归并排序
MSort(MSort(LL.key,.key,LL.key,1,.key,1,LL.length);
}
//快速排序
template
int Partition(SqList& >& LL,int low,int
high)
{//交换顺序表L
中子表key[low]--key[high]
中的记录，枢轴记录到位，并
返回其所在位置，
//此时在它之前（后）的记录均不大（小）于它 type pivotkey;
L.key[0]=.key[0]=LL.key[.key[lowlow];];////
用子表的第一个记录作枢轴记录
pivotkey=pivotkey=LL.key[.key[lowlow];];////
关键字
while(low
从表的两端交替向中间扫描
{
while(low=pivotkey) --high;
L.key[.key[lowlow]=]=LL.key[.key[highhigh];];////
将比枢轴小的记录移至低端
while(low
L.key[.key[highhigh]=]=LL.key[.key[lowlow];];////
将比枢轴大的记录移至高端
}
L.key[.key[lowlow]=]=LL.key[0];.key[0];////
枢轴记录到位
return
low;//
返回枢轴位置
}
template
void QSort(SqList& >& LL,int low,int
high)
{ int mid;//
接收枢轴位置
if(low
{
mid=Partition(mid=Partition(LL,low,high);
QSort(QSort(LL,low,mid-1);,mid-1);////
对低子表进行排序
QSort(QSort(LL,mid+1,,mid+1,highhigh););////对高子表进行排序
}
}
template
void QuitSort(SqList& >& LL)//对顺序表进行快速排序
{
QSort(QSort(LL,1,,1,LL.length);
}
Sort.cpp
void main() {
SqList sl;
LONGLONG start1,finish1,start2,finish2,start3,finish3; CreateSqList(sl);
start1=GetTickCount();
BInsertSort(sl);
finish1=GetTickCount();
delete sl.key;
cout <<"
插入排序平均物理执行时间为
"<
CreateSqList(sl);
start3=GetTickCount();
QuitSort(sl);
