求数组的最大最小值，可以遍历一遍数组，然后分别记录最大值和最小值，这种方法需要的比较次数为2N次。如果想要减少比较次数，可以采用的方法是遍历数组，然后比较相邻元素，把相邻元素的较大值放在后面，较小的放在前面。在从较大值中选取最大值即为整个数组的最大值，从较小值中选取最小值即为整个数组的最小值。这时，需要的比较次数为1.5*N次。
void findmaxmin(int a[],int n)
{
if(a==NULL||n<0)
return ;
int i=0;
int maxe=0x80000000;
int mine=0x7fffffff;
for(i=0;i<n;i+=2)
{
if(i+1<n&&a[i]>a[i+1])
std::swap(a[i],a[i+1]);
}
for(i=0;i<n;i+=2)
{
if(i+1==n)
{
if(a[i]>maxe)
maxe=a[i];
if(a[i]<mine)
mine=a[i];
}
if(a[i]<mine)
mine=a[i];
if(a[i+1]>maxe)
maxe=a[i+1];
}
cout<<maxe<<" "<<mine<<endl;
}
也可以使用分治的方法，先在左半数组求出最大值和最小值，再求右半数组的最大值和最小值，比较两个最大值即可求出整个数组的最大值，比较两个最小值即可求出整个数组的最小值。设比较次数为f(n),有f(2)=1;f(n)=2*f(n/2)+2;
可以求出需要的比较次数是1.5*N-2,比较的次数没有减少。
struct res
{
int min;
int max;
};
res findmaxmin2(int a[],int start,int end)
{
res r;
if(start>=end-1)
{
if(a[start]<a[end])
{
r.min=a[start];
r.max=a[end];
}
else
{
r.min=a[end];
r.max=a[start];
}
return r;
}
int mid=(end-start)/2+start;
res left=findmaxmin2(a,start,mid);
res right=findmaxmin2(a,mid+1,end);
r.max=left.max>right.max?left.max:right.max;
r.min=left.min<right.min?left.min:right.min;
return r;
}