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

实验课程：算法分析与设计 实验名称：实验二 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、 在快速排序中，记录的比较和交换是从两端向中间进行的，关键字较大的记录一次就能交换到后面单元，关键字较小的记录一次就能交换到前面单元，记录每次移动的距离较大，因而总的比较和移动次数较少。实验设备及环境：PC；C/C+的编程环境Visual C+。实验主要步骤：(1) 明确实验目标和具体任务；(2) 理解实验所涉及的分治算法；(3) 编写程序并实现分治算法；(4) 设计实验数据并运行程序、记录运行的结果；实验数据及运行结果、实验结果分析及结论：1、#include using namespace std;int main()int const length=100;int n,x;int alength;cout依次输入数组的长度，数组内容，要查找的数n; /输入数组的长度for(int i=0;iai;cinx; 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; while(left=0) int mid=(left+right)/2; if(x=amid)i=j=mid;break; if(xamid)left=mid+1;elseright=mid-1; if (i=j)&(i=0)cout所找的数据在数组中下标为：iendl;elsei=right;j=left;cout所找的数据不在数组中，其前后下标为：i,jendl;实验结果： 结果分析：数据为数组长度为5，数组内容为1，2，3，4,5和1,2,3,6,8，当要查询的是4时，显示的结果为在第3位和不存在的情况下前后下标为2,3，因而可知程序执行是正确的。2、#include using namespace std;#define num 1000int anum;templatevoid QuickSort(Type a, int p, int r)if (p r)int q = Partition(a, p, r);QuickSort(a, p, q - 1);/ 对左半段排序QuickSort(a, q + 1, r);/ 对右半段排序templateint Partition(Type a, int p, int r)int i = p, j = r + 1;Type x = ap;/ 将x的元素交换到右边区域while (true)while (a+i x);if (i = j)break;swap(ai, aj);ap = aj;aj = x;return j;void main()int n;cout请输入数组大小：n;cout请输入数组的内容并以空格隔开：endl;for(int z=0;zaz;cout从小到大排序后为:;QuickSort(a, 0, n-1);for (int i = 0;i n; +i)if (i != n-1)cout