欢迎来到天天文库
浏览记录
ID:13349422
大小:116.50 KB
页数:4页
时间:2018-07-22
《二分搜索算法和快速排序算法及分治策略》由会员上传分享,免费在线阅读,更多相关内容在行业资料-天天文库。
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(left4、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,intr6、){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<<"从小到大排序后为:";Qui7、ckSort(a,0,n-1);for(inti=0;i
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
此文档下载收益归作者所有