二分搜索算法和快速排序算法及分治策略

二分搜索算法和快速排序算法及分治策略

ID:13349422

大小:116.50 KB

页数:4页

时间:2018-07-22

二分搜索算法和快速排序算法及分治策略_第1页
二分搜索算法和快速排序算法及分治策略_第2页
二分搜索算法和快速排序算法及分治策略_第3页
二分搜索算法和快速排序算法及分治策略_第4页
资源描述:

《二分搜索算法和快速排序算法及分治策略》由会员上传分享,免费在线阅读,更多相关内容在行业资料-天天文库

1、实验课程:算法分析与设计实验名称:实验二C/C++环境及递归算法(综合性/设计性)实验目标:1、熟悉二分搜索算法和快速排序算法;2、初步掌握分治算法;实验任务:掌握分治策略的概念和基本思想。实验题:1、设a[0:n-1]是一个已排好序的数组。请改写二分搜索算法,使得当搜索元素x不在数组中时,返回小于x的最大元素的位置i和大于x的最小元素位置j。当搜索元素在数组中时,I和j相同,均为x在数组中的位置。设有n个不同的整数排好序后存放于t[0:n-1]中,若存在一个下标i,0≤i<n,使得t[i]=i,设计一个有效的算法找到这个下标。要求算法在最坏的情况下的计算时间

2、为O(logn)。2、在快速排序中,记录的比较和交换是从两端向中间进行的,关键字较大的记录一次就能交换到后面单元,关键字较小的记录一次就能交换到前面单元,记录每次移动的距离较大,因而总的比较和移动次数较少。实验设备及环境:PC;C/C++的编程环境VisualC++。实验主要步骤:(1)明确实验目标和具体任务;(2)理解实验所涉及的分治算法;(3)编写程序并实现分治算法;(4)设计实验数据并运行程序、记录运行的结果;实验数据及运行结果、实验结果分析及结论:1、#includeusingnamespacestd;intmain(){intco

3、nstlength=100;intn,x;inta[length];cout<<"依次输入数组的长度,数组内容,要查找的数"<>n;//输入数组的长度for(inti=0;i>a[i];cin>>x;voidBinarySearch(inta[],intn,intx);BinarySearch(a,n,x);return0;}voidBinarySearch(inta[],intn,intx)//n:数组长度,i,j分别表示下标{inti,j,mid=0,left=0;intright=n-1;while(left

4、ight+1&&left>=0){intmid=(left+right)/2;if(x==a[mid]){i=j=mid;break;}if(x>a[mid])left=mid+1;elseright=mid-1;}if((i==j)&&(i>=0))cout<<"所找的数据在数组中下标为:"<

5、在第3位和不存在的情况下前后下标为2,3,因而可知程序执行是正确的。2、#includeusingnamespacestd;#definenum1000inta[num];templatevoidQuickSort(Typea[],intp,intr){if(pintPartition(Typea[],intp,intr

6、){inti=p,j=r+1;Typex=a[p];//将x的元素交换到右边区域while(true){while(a[++i]x);if(i>=j)break;swap(a[i],a[j]);}a[p]=a[j];a[j]=x;returnj;}voidmain(){intn;cout<<"请输入数组大小:"<>n;cout<<"请输入数组的内容并以空格隔开:"<>a[z];cout<<"从小到大排序后为:";Qui

7、ckSort(a,0,n-1);for(inti=0;i

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。