x){for(int j=l.length-1;j>=i+1;j--) {l.data[j+1]=l.data[j];}l.data[i+1]=x;l.length++;printf("没找到 ， 已插入！");print(l);return true;}}}
2.2.10 向左循环移动
10.【2010统考真题】设将n (n >1)个整数存放到一维数组R中 。设计一个在时间和空间两方面都尽可能高效的算法 。将R中保存的序列循环左移p(0
1）给出算法的基本设计思想 。
2）根据设计思想 ， 采用C或C++或Java语言描述算法 ， 关键之处给出注释 。3）说明你所设计算法的时间复杂度和空间复杂度 。
//和第8题一样bool reverse(int start,int end,SqList &l)//翻转 （参考第二题方法） {if(end>=l.length||start>=end)return false;int temp=0;//交换对称位置的数int mid=(start+end)/2;for(int i=0;i<=mid-start;i++)//需要小于等于 ？ 如果< ， 中间两个换不过来 {temp=l.data[start+i];l.data[start+i]=l.data[end-i];l.data[end-i]=temp;} print(l);return true;}void test10(SqList l,int n) //n为循环向左移的数量,顺序表是p+n把n的部分放到p的前面 ， 相当于顺序表整体反转 ， p和n的部分再各自翻转 {reverse(0,l.length-1,l);//整体翻转 reverse(0,n-1,l);//翻转p部分 reverse(n,l.length-1,l);//翻转n部分 }
2.2.11 两个序列的中位数
11.【2011统考真题】一个长度为L(L≥1)的升序序列S ， 处在第[L/2个位置的数称为S的中位数 。例如 ， 若序列S=(11,13,15,17,19) ， 则S的中位数是15 ， 两个序列的中位数是含它们所有元素的升序序列的中位数 。例如 ， 若S1=(2,4,6,8,20) ， 则S和S1的中位数是11 。现在有两个等长升序序列A和B ， 试设计一个在时间和空间两方面都尽可能高效的算法 ， 找出两个序列A和B的中位数 。要求:
1)给出算法的基本设计思想 。
2)根据设计思想 ， 采用C或C++或Java语言描述算法 ， 关键之处给出注释 。3）说明你所设计算法的时间复杂度和空间复杂度 。
void test11(SqList l1,SqList l2)//时间复杂度O(n),空间复杂度O(1){int i=0,j=0; for(int k=0;k<(l1.length+l2.length)/2-1;k++)//直接找到中位数所在位置的那个数 {if(l1.data[i]>l2.data[j])j++;elsei++; }printf("中位数为：%d",l1.data[i]);}
最优算法：
算法的基本设计思想如下 。
分别求两个升序序列A、B的中位数 ， 设为a和b ， 求序列A、B的中位数过程如下:
若a= b ， 则a或b即为所求中位数 ， 算法结束 。
若a 长度相等 。
③若a>b ， 则舍弃序列A中较大的一半 ， 同时舍弃序列B中较小的一半 ， 要求两次舍弃的
长度相等 。
在保留的两个升序序列中 ， 重复过程①、②、③ ， 直到两个序列中均只含一个元素时为止 ， 较小者即为所求的中位数 。
int test11_best(SqList l1,SqList l2)//时间复杂度为O(log2(n)),空间复杂度为O(1){int start1=0,end1=l1.length-1,mid1,start2=0,end2=l2.length-1,mid2;//start,end,mid分别是首位数 ， 末位数 ， 中位数 while(start1!=end1||start2!=end2){mid1=(start1+end1)/2;mid2=(start2+end2)/2;if(l1.data[mid1]==l2.data[mid2]) return l1.data[mid1];//两个中位数相等 ， 结束 if(l1.data[mid1]