分治算法求最值在n个元素中找出最大元素和最小元素

我们可以把这n个元素放在一个数组中，用直接比较法求出

算法如下：void maxmin1(int A,int n,int *max,int *min){    int i;    *min=*max=A;    for(i=0;i <= n;i++)    {        if(A[i]> *max) *max= A[i];        if(A[i] < *min) *min= A[i];    }}上面这个算法需比较2(n-1)次

能否找到更好的算法呢？我们用分治策略来讨论

把n个元素分成两组：A1={A,...,A[int(n/2)]}和A2={A[INT(N/2)+1],...,A[N]}分别求这两组的最大值和最小值，然后分别将这两组的最大值和最小值相比较，求出全部元素的最大值和最小值

如果A1和A2中的元素多于两个，则再用上述方法各分为两个子集

直至子集中元素至多两个元素为止

例如有下面一组元素：-13，13，9，-5，7，23，0，15

用分治策略比较的算法如下：void maxmin2(int A,int i,int j,int *max,int *min)/*A存放输入的数据，i，j存放数据的范围，初值为0，n-1，*max,*min 存放最大和最小值*/{    int mid,max1,max2,min1,min2;    if (j==i)    {        最大和最小值为同一个数;        return;    }    if (j-1==i)    {        将两个数直接比较，求得最大和最小值；        return；    }    mid=(i+j)/2;    求i~mid之间的最大最小值分别为max1，min1;    求mid+1~j之间的最大最小值分别为max2，min2;    比较max1和max2，大的就是最大值;    比较min1和min2，小的就是最小值;}

以上内容由大学时代综合整理自互联网，实际情况请以官方资料为准。