分治法实现归并排序算法算法设计与分析实验报告
- 格式：doc
- 大小：75.00 KB
- 文档页数：8
算法设计与分析实验报告
实验名称 分治法实现归并排序算法 评分
实验日期 年 月 日 指导教师
姓名 专业班级 学号
一.实验要求
1.了解用分治法求解的问题：当要求解一个输入规模为n，且n的取值相当大的问题时，
如果问题可以分成k个不同子集合，得到k个不同的可独立求解的子问题，其中1
2.掌握分治法的一般控制流程。
DanC(p,q)
global n，A[1:n]; integer m,p,q; // 1pqn
if Small(p,q) then return G(p,q);
else m=Divide(p,q); // pm
return Combine(DanC(p,m),DanC(m+1,q));
endif
end DanC
3．实现典型的分治算法的编程与上机实验，验证算法的时间复杂性函数。
二.实验内容
1.编程实现归并排序算法，程序中加入比较次数的计数功能，输出排序结果和比较次数。
2.输入10组相同的数据，验证排序结果和完成排序的比较次数。
3.与复杂性函数所计算的比较次数比较。
4.用表格列出比较结果。
5.给出文字分析。
三.程序算法
1. 归并排序算法
procedure MERGESORT(low，high)
//A(low；high)是一个全程数组，它含
有high-low+1≥0个待排序的元素//
integer low，high；
if low
call MERGESORT(low，mid) //将一个子集合排序//
call MERGESORT(mid+1，high) //将另一个子集合排序
call MERGE(low，mid，high) //归并两个已排序的子集合//
endif
end MERGESORT
归并两个已排序的集合
procedure MERGE(low，mid，high)
//A(low：high)是一个全程数组//
//辅助数组B(low；high)//
integer h，i，j，k；
h←low；i←low；j←mid+1；
while h≤mid and j≤high do //当两个集合都没取尽时//
if A(h)≤A(j) then B(i) ←A(h)；h←h+1
else B(i) ←A(j)；j←j+1
endif
i←i+1
repeat
if h>mid then
for k←j to high do //处理剩余的元素//
B(i) ←A(k)；i←i+1
repeat
else for k←h to mid do
B(i) ←A(k)；i←i+1
repeat
endif
将已归并的集合复制到A
end MERGE
2. 快速排序算法
QuickSort(p,q)
//将数组A[1:n]中的元素
A[p], A[p+1], , A[q]按不降次序排列，
并假定A[n+1]是一个确定的、且大于
A[1:n]中所有的数。//
int p,q; global n, A[1:n];
if p
j=Partition(p, q+1); // 划分后j成为划分元素的位置 QuickSort(p,j-1);
QuickSort(j+1,q);
endif
end QuickSort
procedure PARTITION(m，p)
//退出过程时，p带着划分元素所在的下标位置。//
integer m，p，i；global A(m：p-1)
v←A(m)；i←m //A(m)是划分元素//
loop
loop i←i+1 until A(i)≥v repeat //i由左向右移//
loop p←p-1 until A(p)≤v repeat //p由右向左移//
if i
then call INTERCHANGE(A(i)，A(p)) //A(i)和A(p)换位//
else exit
endif
repeat
A(m) ←A(p)；A(p) ←v //划分元素在位置p//
End PARTITION
四.程序代码
1. 归并排序
#include
#include
#include
#include
#define M 11
typedef int KeyType;
typedef int ElemType;
struct rec{
KeyType key;
ElemType data;
};
typedef rec sqlist[M];
class guibing{
public:
guibing(sqlist b)
{
for(int i=0;i
r[i]=b[i]; }
void output(sqlist r,int n)
{
for(int i=0;i
cout<
cout<
}
void xuanze(sqlist b,int m,int n)
{
int i,j,k;
for(i=m;i
{
k=i;
for(j=i;j
if(b[k].key>b[j].key) k=j;
if(k!=i)
{
rec temp=b[k];
b[k]=b[i];
b[i]=temp;
}
}
}
void merge(int l,int m,int h,sqlist r2)
{
xuanze(r,l,m);
xuanze(r,m,h);
output(r,M);
int i,j,k;
k=i=l;
for(j=m;i
{
if(r[i].key<=r[j].key)
{
r2[k]=r[i];
i++;
}
else {
r2[k]=r[j];
j++;
}
output(r2,M);
}
while(j
{
r2[k]=r[j];
j++;
k++;
}
while(i<=m)
{
r2[k]=r[i];
i++;
k++;
}
output(r2,M);
}
private:
sqlist r;
};
void main()
{
cout<<"guibingfa1运行结果:\n";
sqlist a,b;
int i,j=0,k=M/2,n=M;
srand(time(0));
for(i=0;i
{
a[i].key=rand()%80;b[i].key=0;
}
guibing gx(a);
cout<<"排序前数组:\n";
gx.output(a,M);
cout<<"数组排序过程演示:\n";
gx.merge(j,k,n,b); cout<<"排序后数组:\n";
gx.output(b,M);
cin.get();
}
2. 快速排序
#include
#include
#include
#include
#define MAXI 10
typedef int KeyType;
typedef int ElemType;
struct rec{
KeyType key;
ElemType data;
};
typedef rec sqlist[MAXI];
class kuaisu
{
public:
kuaisu(sqlist a,int m):n(m)
{
for(int i=0;i
}
void quicksort(int s,int t)
{
int i;
if(s
i=part(s,t);
quicksort(s,i-1);
quicksort(i+1,t);
}
else return;
}
int part(int s,int t)
{
int i,j;
rec p;
