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

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

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