分治法——查找问题 —— 寻找一个序列中第k小的元素和查找最大和次大元素

查找问题：

对于给定的含有n个元素的无序序列，求这个序列中第k（1<=k<=n）小的元素

分析思路：

假设无序序列存放在a[0 … n-1]中，若将a递增排序，则第k小的元素为a[k-1].

对于无序序列a[s … t]，在其中查找第k小的元素

（1）若s>=t，其中只有一个元素或没有任何元素，

（2）若s=t且s=k-1，表示只有一个元素，a[k-1]即为所求结果

（3）s<t，表示该序列有两个或两个以上的元素，以基准为中心将其划分为a[s … i-1]和a[i+1 … t]两个子序列，基准a[i]即已归位，a[s … i-1]中所有元素均小于a[i],a[i+1 … t]中所有元素均大于a[i],即a[i]为第i+1小的元素存在以下三种情况

①若k-1=i,a[i]为所求结果

②若k-1<i,第k小元素在a[s … i-1]序列中

③若k-1>i,第k小元素在a[i+1 … t]序列中

代码：

#include<stdio.h>int QuickSelect(int a[],int s,int t,int k){int i=s,j=t;int tmp;if(s<t){//区间内至少存在2个以上的元素 tmp=a[s]; //用区间第一个记录作为基准while(i!=j){//区间两端指针向中间移动，直到i=j为止 while(j>i&&a[j]>=tmp) j--; //从右向左扫描，找到第一个关键字小于tmp的a[j] a[i]=a[j]; //将a[j]移动到a[i]的位置while(i<j&&a[i]<=tmp)i++; //从左向右扫描，找到第一个关键字大于tmp的a[i] a[j]=a[i]; //将a[i]移动到a[j]的位置 } a[i]=tmp;if(k-1==i)return a[i];else if(k-1<i)return QuickSelect(a,s,i-1,t); //在左区间中递归查找elsereturn QuickSelect(a,i+1,t,k); //在右区间中递归查找 }else if(s==t&&s==k-1)//区间中只有一个元素return a[k-1]; }int main(){int n=10;int k,e;int a[]={2,5,1,7,10,6,9,4,3,8};for(k=1;k<n;k++){e=QuickSelect(a,0,n-1,k);printf("第%d 小的元素：%d\n",k,e);}}

问题二：查找最大和次大元素

对于给定的含有n个元素的无序序列，求这个序列中的最大和次大元素

分析思路：

（1）若a[low … high]中含有一个元素，则max1=a[low],max2=-INF(负无穷大)

（2）若a[low … high]中含有两个元素，则max1=max{a[low],a[high]};max2=min{a[low],a[high]};

（3）若a[low … high]中含有两个以上元素，按中间位置mid=(low+high)/2划分为a[low … mid] 和a[mid+1 … high]两个区间，求出左区间的最大元素lmax1和次大元素lmax2;再求出右区间的最大元素rmax1和次大元素rmax2

若lmax1>rmax1则max1=lmax1,max2=max{lmax2,rmax1};否则max1=rmax1,max2=max{lmax1,rmax2}

举例：

对于a[0 … 4]={5,2,1,4,3},mid=(0+4)/2,划分为左区间a[0 … 2]={5,2,1}和右区间a[3,4]={4,3}

左区间：lmax1=5,lmax2=2

右区间：rmax1=4,rmax2=3

再进行比较

代码：

void solve(int a[],int low,int high,int &max1,int &max2){if(low==high){//只有一个元素 max1=a[low];max2=-INF;}else if(low=high-1) //有两个元素{max1=max(a[low],a[high]);max2=min(a[low],a[high]);} else {//两个以上元素 int mid=(low+high)/2;int lmax1,lmax2;solve(a,low,mid,lmax1,lmax2); //左区间求 int rmax1,rmax2;solve(a,mid+1,high,rmax1,rmax2); //右区间求 if(lmax1>rmax1){max1=lmax1;max2=max(lmax2,rmax1);}else{max1=rmax1;max2=max(rmax2,lmax1);}}}