版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
实验报告2016/2017学年第二学期)课程名称算法解析与设计实验名称分治策略实验时间2017年3月30日指导单位计算机学院软件工程系指导教师张怡婷学生姓名霍淇滨班级学号学院(系)计算机学院专业软件工程实验报告实验名称分治策略指导教师张怡婷实验种类考据型(第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){inti=left,j=right+1;do{doi++;while(l[i]<l[left]);doj--;while(l[j]>l[left]);if(i<j)Swap(i,j);}while(i<j);Swap(left,j);returnj;}源.app#include<iostream>#include"标头.h"usingnamespacestd;voidmain(){intn=10;SortableListmy1(n);SortableListmy2(n);my1.Input();my2.Input();my1.MergeSort();my2.QuickSort();my1.Output();my2.Output();}二、采用基于“五元中值组取中值切割法”(median-of-median-of-fivepartitioning)的线性时间选择算法,找出N个元素会集S中的第k个最小的元素,使其在线性时间内解决。标头.h#include<iostream>usingnamespacestd;enumResultCode{OutOfBounds,Success};classSortableList{public:SortableList(intmSize);~SortableList();voidInput();voidOutput();ResultCodeSelect(int&x,intk);private:int*l;intmaxSize;intn;voidSwap(inti,intj);voidInsertSort(intleft,intright);intPartition(intleft,intright);intSelect(intk,intleft,intright,intr);};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::Swap(inti,intj){intc=l[i];l[i]=l[j];l[j]=c;}intSortableList::Partition(intleft,intright){inti=left,j=right+1;do{doi++;while(l[i]<l[left]);doj--;while(l[j]>l[left]);if(i<j)Swap(i,j);}while(i<j);Swap(left,j);returnj;}ResultCodeSortableList::Select(int&x,intk){if(n<=0||k>n||k<=0)returnOutOfBounds;intj=Select(k,0,n-1,5);x=l[j];returnSuccess;}intSortableList::Select(intk,intleft,intright,intr){intn=right-left+1;if(n<=r){//若问题足够小,使用直接插入排序InsertSort(left,right);returnleft+k-1;//取其中的第k小元素,其下标为left+k-1}for(inti=1;i<=n/r;i++){InsertSort(left+(i-1)*r,left+i*r-1);//二次取中规则求每组的中间值Swap(left+i-1,left+(i-1)*r+(int)ceil((double)r/2)-1);//将每组的中间值交换到子表前部集中存放}//求二次中间值,其下标为jintj=Select((int)ceil((double)n/r/2),left,left+(n/r)-1,r);Swap(left,j);//二次中间值为枢纽元,并换至left处j=Partition(left,right);//对表(子表)进行分划操作if(k==j-left+1)returnj;//返回第k小元素下标elseif(k<j-left+1)returnSelect(k,left,j-1,r);//在左子表求第k小元素elsereturnSelect(k-(j-left+1),j+1,right,r);//
在右子表求第
k-(j-left+1)
小元素}voidSortableList::InsertSort(intleft,intright){for(inti=left+1;i<=right;i++){intj=i;inttemp=l[i];while(j>left&&temp<l[j-1]){l[j]=l[j-1];j--;}l[j]=temp;}
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 二零二五年度水电工程招投标合同5篇
- 2025年度新能源车辆采购及运营合同3篇
- 2024食堂食品安全保障与供货合同
- 2025年度智能家居系统采购与施工安装合同3篇
- 年度科创大数据市场分析及竞争策略分析报告
- 年度分步重复光刻机竞争策略分析报告
- 2025年私人房产交易合同范本下载6篇
- 2024-2025学年高中英语Unit4Learningeffectively单元复习课教师用书教案新人教版选修10
- 二零二四年南京二手房买卖合同及物业交接细则3篇
- 二零二五年度新能源电动车销售及分期付款协议2篇
- GA 1551.5-2019石油石化系统治安反恐防范要求第5部分:运输企业
- 拘留所教育课件02
- 冲压生产的品质保障
- 《肾脏的结构和功能》课件
- 2023年湖南联通校园招聘笔试题库及答案解析
- 上海市徐汇区、金山区、松江区2023届高一上数学期末统考试题含解析
- 护士事业单位工作人员年度考核登记表
- 天津市新版就业、劳动合同登记名册
- 产科操作技术规范范本
- 人教版八年级上册地理全册单元测试卷(含期中期末试卷及答案)
- 各种焊工证件比较和释义
评论
0/150
提交评论