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

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

2、比较和交换是从两端向中间进行的，关键字较大的记录一次就能交换到后面单元，关键字较小的记录一次就能交换到前面单元，记录每次移动的距离较大，因而总的比较和移动次数较少。实验设备及环境：pc；c/c+的编程环境visual c+。实验主要步骤：(1) 明确实验目标和具体任务；(2) 理解实验所涉及的分治算法；(3) 编写程序并实现分治算法；(4) 设计实验数据并运行程序、记录运行的结果；实验数据及运行结果、实验结果分析及结论：1、#include <iostream>using namespace std;int main()int const length=100;int n,x;in

3、t alength;cout<<"依次输入数组的长度，数组内容，要查找的数"<<endl;cin>>n; /输入数组的长度for(int i=0;i<n;i+)cin>>ai;cin>>x; void binarysearch(int a,int n,int x); binarysearch(a, n, x);return 0;void binarysearch(int a,int n,int x) /n:数组长度，i，j分别表示下标 int i,j,mid=0,left=0; int right=n-1;

4、while(left<right+1&&left>=0) int mid=(left+right)/2; if(x=amid)i=j=mid;break; if(x>amid)left=mid+1;elseright=mid-1; if (i=j)&&(i>=0)cout<<"所找的数据在数组中下标为："<<i<<endl;elsei=right;j=left;cout<<"所找的数据不在数组中，其前后下标为："<<i<<

5、9;,'<<j<<endl;实验结果： 结果分析：数据为数组长度为5，数组内容为1，2，3，4,5和1,2,3,6,8，当要查询的是4时，显示的结果为在第3位和不存在的情况下前后下标为2,3，因而可知程序执行是正确的。2、#include <iostream>using namespace std;#define num 1000int anum;template<class type>void quicksort(type a, int p, int r)if (p < r)int q = partition(a, p, r);q

6、uicksort(a, p, q - 1);/ 对左半段排序quicksort(a, q + 1, r);/ 对右半段排序template<class type>int partition(type a, int p, int r)int i = p, j = r + 1;type x = ap;/ 将<x的元素交换到左边区域/ 将>x的元素交换到右边区域while (true)while (a+i < x);while (a-j > x);if (i >= j)break;swap(ai, aj);ap = aj;aj = x;return j;void main()int n;cout<<"请输入数组大小："<<endl;cin>>n;cout<<"请输入数组的内容并以空格隔开："<<endl;for(int z=0;z<n;z+)cin>>az;cout<<"从小到大排序后为:"quicksort(a, 0, n-1);for (int i = 0;i < n; +i)if (i != n-1)cout << ai << &