算法--分治策略.doc

《算法--分治策略.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、实验报告（2016/2017学年第二学期）课程名称算法分析与设计实验名称分治策略实验时间2017年3月30日指导单位计算机学院软件工程系指导教师张怡婷学生姓名霍淇滨班级学号B15041236学院(系)计算机学院专业软件工程实验报告实验名称分治策略指导教师张怡婷实验类型验证型（第4个实验密码算法是“设计型”）实验学时2实验时间2017-3-30一、实验目的和任务理解分治法的算法思想，阅读实现书上已有的部分程序代码并完善程序，加深对分治法的算法原理及实现过程的理解二、实验环境(实验设备)VisualStudio20158三、实验原理及内容（包括操作过程、结果分析等）一、用分治法实

2、现一组无序序列的两路合并排序和快速排序。要求清楚合并排序及快速排序的基本原理，编程实现分别用这两种方法将输入的一组无序序列排序为有序序列后输出。标头.h#includeusingnamespacestd;classSortableList{public:SortableList(intmSize);~SortableList();voidInput();//输入数组voidOutput();//输出数组voidMergeSort();//两路合并排序voidQuickSort();//快速排序private:int*l;//数组指针intmaxSize;/

3、/数组最大长度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(){de

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

5、:MergeSort(intleft,intright){if(left

6、;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)8{intc=l[i];l[i]=l[j];l[j]=c;}voidSortableList::QuickSort(intleft,intright){if(left

7、,j-1);QuickSort(j+1,right);}}intSortableList::Parition(intleft,intright){inti=left,j=right+1;do{doi++;while(l[i]l[left]);if(i#include"标头.h"usingnamespacestd;