AU瑯唸Z磬实验报告（2016/2017 学年 第一学期）课程名称算法分析与设计实验名称分治策略实验时间2016 年 10 月 18 日指导单位计算机学院软件教学中心指导教师季一木学生姓名周文超班级学号B14041527学院（系）计算机学院、软件学院专 业软件工程实验报告实验名称分治策略指导教师季一木实验类型验证实验学时2实验时间2016.10.18实验目的和任务1•理解分治法的算法思想，阅读实现书上已有的部分程序代码并完善程 加深对分治法的算法原理及实现过程的理解i^B M： ■2•用分治法实现一组无序序列的两路合并排序和快速排序要求清楚合并排序及快速排序的基本原理，编程实现分别用这两种方法将输入的一组 无序序列排序为有序序列后输出实验环境（实验设备）算法设计与分析课本 笔记本电脑VC++6.0三、实验原理及内容（包括操作过程、结果分析等）实验原理运用分治法：无序-> 部分有序-> 整体有序SM MH MV MB MB BM HH ■■■ BM ^BT MB BB MH! MM MM MH MB!归并排序中“分”与“合”的过程是结合在一起的，即每一趟都在做“分” 与“合”的工作，并不是先“分”完再“合”基本程序(一)两路合并排序#in cludeclass 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::l nput(){for(i nt i = O;i >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++];elsetemp[k++]=l[ j++];while(i<=mid) temp[k++]=l[i++];while( j<=right)temp[k++]=l[ j++];for(i = O,k=left;k<=right;)l[k++]=temp[i++];}void SortableList::MergeSort(){MergeSort(0, n-1);void SortableList::MergeSort(int left,int right){if(leftclass 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 *1; //动态生成一维数组int maxSize; // 线性表的最大表长int n; //线性表的实际长度｝； void SortableList::l nput(){for(i nt i = O;i >l[i];n++;}} void SortableList::Swap(i nt i,i nt j){int c = l[i];l[i] = l[ j];l[j] = c;}int SortableList::Partition(int left,int right){// 前置条件：left<=rightint i = left,j = right + 1;do{do i++;while(l[i]l[left]);if(i
快速排序又称分划交换排序，分别将两个子序列拍成有序序列，则整个序列也就成了 有序序列首先要掌握基本的排序思想，然后把逻辑语言转化成程序语言，参考网上的各种答案 优化自己的算法程序结合所学知识七、指导教师评语成绩批阅人日期14。