文档介绍：《算法设计与分析》、排序和查找是经常遇到的问题。按照要求完成以下各题:⑴对数组A={15,29,135,18,32,1,27,25,5},用快速排序方法将其排成递减序。解:(1)第一步:15291351832127255第二步:29135183227251515第三步:13532291827251551第四步:13532292725181551请描述递减数组进行二分搜索的基本思想,并给出非递归算法。解:基本思想:首先将待搜索元素v与数组的中间元素A[彳[进行比较,如果[彳],则在前半部分元素中搜索v;若=中],则搜索成功;否则在后半部分数组中搜索V。非递归算法:输入:递减数组A[left:right],待搜索元素v。输出:v在A中的位置pos,或者不在A中的消息(・1b步骤:intBinarySearch(intA[],intleft,intright,intv){intmid;while(left<=right)mid=int((left+right)/2);if(v==A[mid])returnmid;elseif(v>A[mid])right=mid・1;elseleft=mid+1;}return-1;}给出上述算法的递归算法。解:输入:递减数组A[left:right],待搜索元素vo输出:v在A中的位置pos,或者不在A中的消息L步骤:【3分】intBinarySearch(intA[],intleft,intright)ntv){intmid;if(left<=right){mid=int((left+right)/2);if(v==A[mid])returnmid;elseif(v>A[mid])returnBinarySearch(A,left,mid・1,v);elsereturnBinarySearch(A,mid+1,right,v);elsereturn-1;}使用上述算法对(1)所得到的结果搜索如下元素,并给出搜索过程:18,31,135o解:搜索18:首先与27比较,18<27,在后半部分搜索;再次与18比较,搜索到,返回5。搜索31:首先与27比较,31>27,在前半部分搜索;再次32比较,3K32,在后半部分搜索,与29比较,31>29,此时只有一个元素,未找到,返回搜索135:首先与27比较,135>27,在前半部分搜索;再次32比较,135>32,在前半部分搜索;与135比较,相同,返回Oo二、排序和查找是常用的计算机算法。按照要求完成以下各题:(1)对数组A={15,9,115,118,3,90,27,25,5},使用合并排序方法将其排成递减序。(2)若改变二分搜索法为三分搜索法,即从一个递减序列A中寻找元素Z,先与元素川巴]比较,若Z>A[-],则在前面口个元素中寻找Z;否则与A[岂]比较,总之使余下的序列为匸]个元素。给出该方法的伪代码描述。(3)使用上述算法对(1)所得到的结果搜索如下元素,并给出搜索过程:"8,31,25o解:(1)第一步:159"5"839027255第二步:159"8笛590327255第三步:"8"5**********第四步:"811590272515935第五步:们8"590272515953(2)输入:递减数组A[left:right],待搜索元素V。输出:v在A中的位置pos,或者不在A中的消息(・1L步骤:intBinarySearch(intA[],intleftjntright,intv){intmid;while(left<=right){first=left+(right-left+1)/3;second=left+(right-left+1)/3*2;if(v==A[first])returnfirst;elseif(v>A[first])right=first-1;elseif(v==A[second])returnsecond;elseif(v>A[second]){left=first+1;right=second-1;}elseleft=second+1;}return-1;(3)搜索118:118>27,所以right=3;118>115,所以right=1;118=118,找到。搜索31:31>27,所以right=3;31<90,所以left=4,结束,未找到。搜索25:9<25<27,所以left=5,right=6;25=25,找到。三、Dijkstra算法求单源最短路径d[u]:s到u的距离p[u]:记录前一节点信息lnit-single-source(G,s)foreachvertexveV[G]do{d[v]=<»;p[v]=NIL}d[s]=0Relax(u,v,w)ifd[v]>d[u]+w(u,v)the