分治法求数组最大最小值

常规的做法是遍历一次，分别求出最大值和最小值，但我这里要说的是分治法(Divide and couquer)，将数组分成左右两部分，先求出左半部份的最大值和最小值，再求出右半部份的最大值和最小值，然后综合起来求总体的最大值及最小值。这是个递归过程，对于划分后的左右两部分，同样重复这个过程，直到划分区间内只剩一个元素或者两个元素。

#include <stdio.h>
#include <stdlib.h>
void maxandmin(int a[],int left,int right,int *maxvalue,int *minvalue)
{
int mid;
if(left == right)
{
*maxvalue=a[left];
*minvalue=a[left];
return;
}
if(left+1 == right)
{
if(a[left]<=a[right])
{
*maxvalue=a[left];
*minvalue=a[right];
}
else
{
minvalue=&a[right];
maxvalue=&a[left];
}
return;
}
mid=(left+right)/2;
int lmax,lmin;
maxandmin(a,left,mid,&lmax,&lmin);
int rmax,rmin;
maxandmin(a,mid+1,right,&rmax,&rmin);
if(lmax>rmax)
*maxvalue=lmax;
else
*maxvalue=rmax;
if(lmin>rmin)
*minvalue=rmin;
else
*minvalue=lmin;
// printf("maxvalue=%d,
minvalue=%d
",*maxvalue,*minvalue);
}
int main()
{
int a[13]= {2,4,70,97,127,304,67,77,81,83,99,10,209};
int b[6]=
{1,2,5,7,9,11};
int c[19];
int i;
int max;
int min;
maxandmin(a,0,12,&max,&min);
printf("max=%d,
min=%d",max,min);
system("PAUSE");
return 0;
}

最后

以上就是爱撒娇外套为你收集整理的分治法求数组最大最小值的全部内容，希望文章能够帮你解决分治法求数组最大最小值所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。