算法分治策略.docx

实验报告
（2016/2017学年第二学期）

课程名称算法分析与设计实验名称分治策略实验时间2017年3月30日指导单位计算机学院软件工程系指导教师张怡婷

学生姓名霍淇滨班级学号B15041236学院(系)计算机学院专业软件工程
实验报告
实验名称分治策略指导教师张怡婷实验类型验证型（第4个实验密码算法是“设计型”）实验学时2实验时间2017-3-30实验目的和任务
理解分治法的算法思想，阅读实现书上已有的部分程序代码并完善程序，加深对分治法的算法原理及实现过程的理解

实验环境(实验设备)
VisualStudio2015三、实验原理及内容（包括操作过程、结果分析等）
一、用分治法实现一组无序序列的两路合并排序和快速排序。要求清楚合并排序及快速排序的基本原理，编程实现分别用这两种方法将输入的一组无序序列排序为有序序列后输出。
标头.h
#include<iostream>
usingnamespacestd;
classSortableList
{
public:
SortableList(intmSize);
~SortableList();
voidInput();//输入数组
voidOutput();//输出数组
voidMergeSort();//两路合并排序
voidQuickSort();//快速排序
private:
int*l;//数组指针
intmaxSize;//数组最大长度
intn;//数组已有元素个数
voidMergeSort(intleft,intright);
voidMerge(intleft,intmid,intright);
voidSwap(inti,intj);//交换函数
voidQuickSort(intleft,intright);
intParition(intleft,intright);//分割函数
};

SortableList::SortableList(intmSize)
{
maxSize=mSize;
l=newint[maxSize];
n=0;
}

SortableList::~SortableList(){ delete[]l;}

voidSortableList::Input()
{
cout<<"请输入待排序的数组\n";
for(inti=0;i<maxSize;i++){
cin>>l[i];
if(l[i]==-1)
break;
n++;
}

}

voidSortableList::Output()
{
for(inti=0;i<n;i++)
cout<<l[i]<<"";
}

voidSortableList::MergeSort(){MergeSort(0,n-1);}

voidSortableList::QuickSort(){QuickSort(0,n-1);}

voidSortableList::MergeSort(intleft,intright)
{
if(left<right){
intmid=(left+right)/2;
MergeSort(left,mid);
MergeSort(mid+1,right);
Merge(left,mid,right);

}
}

voidSortableList::Merge(intleft,intmid,intright)
{
int*temp=newint[right-left+1];
inti=left,j=mid+1,k=0;
while((i<=mid)&&(j<=right))
if(l[i]<=l[j])temp[k++]=l[i++];
elsetemp[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++];

}

voidSortableList::Swap(inti,intj)
{
intc=l[i];
l[i]=l[j];
l[j]=c;
}

voidSortableList::QuickSort(intleft,intright)
{
if(left<right){
intj=Parition(left,right);
QuickSort(left,j-1);
QuickSort(j+1,right);
}
}

intSortableList::Parition(intleft,intright)
{
i