实验报告
（2016/2017学年第一学期）
课程名称
算法分析与设计
实验名称
分治策略
实验时间
2016 年 10 月 18 日
指导单位
计算机学院软件教学中心
指导教师
季一木
学生姓名
周文超
班级学号
学院（系）
计算机学院、
软件学院
专 业
软件工程
实验报告
实验名称
分治策略
指导教师
季一木
实验类型
验证
实验学时
2
实验时间
2016.10.18
实验目的和任务
理解分治法的算法思想，阅读实现书上已有的部分程序代码并完善程 序，加深对分治法的算法原理及实现过程的理解。
用分治法实现一组无序序列的两路合并排序和快速排序。要求清楚
U E3 n C3 E3 C3 n U C3 SC3 E3 O C3 E3 U E3 iO C3 E3 0 C3 n U C3 C3 E3 O C3 E3 U C3 O C3 E3 0 C3 E3 U C3 0 C3 E3O C3 E3 C3 = C3 E3 0 C3 l""IL C3 C3 E3 0C3 n U C3 n C3 E3 0 C3 合并排序及快速排序的基本原理，编程实现分别用这两种方法将输入的一组 无序序列排序为有序序列后输出。
H^T MB ■
、、实验环境（实验设备）
算法设计与分析课本 笔记本电脑
VC++6.0
三、实验原理及内容(包括操作过程、结果分析等)
实验原理
运用分治法：无序-> 部分有序-> 整体有序
归并排序中“分”与“合”的过程是结合在一起的，即每一趟都在做“分”
与“合”的工作，并不是先“分”完再“合”
基本程序
(一)两路合并排序
#in clude<iostream.h>
class SortableList{
public:
SortableList(i nt mSize) // 构造函数
{
maxSize = mSize;
l = new in t[maxSize];
n = 0;
}
~SortableList(){delete[]l;} // 析构函数
void In put();
void Merge(i nt left,i nt mid,i nt right);
void MergeSort();
void MergeSort(int left,int right);
void Output();
private:
int *l; // 动态生成一维数组
int maxSize; // 线性表的最大表长
int n; // 线性表的实际长度
};
void SortableList::I nput(){
for(i nt i = 0;i<maxSize;i++){
ci n> >l[i];
n++;
}
}
void SortableList::Merge(i nt left,i nt mid,i nt right){ int *temp = new in t[right-left+1];
int i = left,j = mid +1,k = 0; while((i<=mid)&&(j<=right)) if(l[i]<=l[j])
temp[k++]=l[i++];
else
temp[k++]=l[j++];
while(i<=mid) temp[k++]=l[i++];
while(j<=right) temp[k++]=l[j++];
for(i = 0,k=left;k<=right;) l[k++]=temp[i++];
}
void SortableList::MergeSort(){ MergeSort(0, n-1);
}
void SortableList::MergeSort(int left,int right){
if(left<right){〃 若序列的长度超过1，则划分成两个子序列
将待排序的序列一分为二对左序列排序对右序列排序将两个有序子序列合并成一个有序序列int mid =
将待排序的序列一分为二
对左序列排序
对右序列排序
将两个有序子序列合并成一个有序序列
MergeSort(mid+1,right);// Merge(left,mid,right);// } }
void SortableList::Output(){ for(i nt i = O;i<maxSize;i++){ cout<<l[i]<<"";
}
}
void mai n(){
SortableList l(10);
cout<<"请输入 10 个数："<<endl; l.I nput();
l.MergeSort();
cout<<"排序后是："<<endl; l.0utput();
}
(二)快速排序
#in clude<iostream.h>
class SortableList{
public:
SortableList(i nt mSize) // 构造函数
{
maxSize = mSize;
l = new in t[maxSize];
n = 0;
}
~SortableList(){delete[]l;} // 析构函数
void In put();
void Swap(i nt i,i nt j);
int Partiti on (i nt left,i nt right);
void QuickSort(int left,int right);
void QuickSort();
void Output();
private:
int *l; // 动态生成一维数组
int maxSize; // 线性表的最大表长
int n; // 线性表的实际长度
};
void SortableList::I nput(){
for(i nt i = 0;i<maxSize;i++){
ci n> >l[i];
n++;
}
}
void SortableList::Swap(i nt i,i nt j){
int c = l[i];
l[i] = j
l[j] = c;
}
int SortableList::Partition(int left,int right){
// 前置条件：left<=right
int i = left,j = right + 1;
do{
do i++;while(l[i]<l[left]);
do j--;while(l[j]>l[left]); if(i<j)Swap(i,j);
}while(i<j); Swap(left,j);
return j;
}
void SortableList::QuickSort(){
Quicksort? n-1);
}
void SortableList::QuickSort(int left,int right){
范围内的序列进行分划if(left<right){ // 当序列长度大于1时，需进行分割
范围内的序列进行分划
int j = Partitio n(left,right);〃 对[left,right]
QuickSort(left,j-1);〃 对左子序列实施快速排序
QuickSort(j+1,right);// 对右子序列实施快速排序
}
}
void SortableList::Output(){
for(i nt i = O;i<maxSize;i++){ cout<<l[i]<<"";
}
}
void mai n(){
SortableList l(10);
cout<<"请输入 10 个数："<<endl;
l.I nput();
l.QuickSort();
cout<<"排序后是："<<endl;
l.Output();
}
实验结果
两路合并排序
快速排序
六、实验小结（包括问题和解决方法、心得体会等）
合并排序的基本运算是把两个或多个有序序列合并成一个有序序列。
快速排序又称分划交换排序，分别将两个子序列拍成有序序列，则整个序列也就成了 有序序列。
首先要掌握基本的排序思想，然后把逻辑语言转化成程序语言，参考网上的各种答案 优化自己的算法程序结合所学知识。
七、指导教师评语
成绩
批阅人
日期
欢迎您的下载，
资料仅供参考!
致力为企业和个人提供合同协议，策划案计划书，学习资料等等
打造全网一站式需求