整型数组处理算法（四）求数组的最大值和最小值

求数组的最大值和最小值，返回值在maxValue和minValue。

方法一：

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

具体实现如下：

// 求数组的最大值和最小值，返回值在maxValue和minValue
void MaxandMin(int *a, int l, int r, int& maxValue, int& minValue)
{
    if(l == r) // l与r之间只有一个元素
    {
        maxValue = a[l] ;
        minValue = a[l] ;
        return ;
    }
	
    if(l + 1 == r) // l与r之间只有两个元素
    {
        if(a[l] >= a[r])
        {
            maxValue = a[l] ;
            minValue = a[r] ;
        }
        else
        {
            maxValue = a[r] ;
            minValue = a[l] ;
        }
        return ;
    }
	
    int m = (l + r) / 2 ; // 求中点

	
    int lmax ; // 左半部份最大值
    int lmin ; // 左半部份最小值
    MaxandMin(a, l, m, lmax, lmin) ; // 递归计算左半部份
	
    int rmax ; // 右半部份最大值
    int rmin ; // 右半部份最小值
    MaxandMin(a, m + 1, r, rmax, rmin) ; // 递归计算右半部份
	
    maxValue = max(lmax, rmax) ; // 总的最大值
    minValue = min(lmin, rmin) ; // 总的最小值
}

方法二：

用循环，实现如下：

void MaxandMinByLoop(int *a, int nCount, int& maxValue, int& minValue)
{
	maxValue = a[0];
	minValue = a[0];
	for (int i=1; i<nCount; i++)
	{
		if (maxValue<a[i])
		{
			maxValue = a[i];
		}
		else if (maxValue>a[i])
		{
			minValue = a[i];
		}
	}
}

测试代码：

int main()
{
	int* a= new int[6];
	int* b= new int[3];
	
	a[0]=2;
	a[1]=5;
	a[2]=3;
	a[3]=4;
	a[4]=7;
	a[5]=0;
	
	b[0]=8;
	b[1]=9;
	b[2]=6;
	
	int MaxNum;
	int MinNm;
	
	//MaxandMin(b, 0, 2, MaxNum, MinNm);
	MaxandMin(a, 0, 5, MaxNum, MinNm);

	cout << "MinNm=" << MinNm << ",MaxNum=" << MaxNum <<endl;

	MaxandMinByLoop(b, 3, MaxNum, MinNm);
	//MaxandMinByLoop(a, 6, MaxNum, MinNm);

	cout << "MinNm=" << MinNm << ",MaxNum=" << MaxNum <<endl;
	
	delete[] a;
	a=NULL;
	delete[] b;
	b=NULL;
	
	cout << endl;
	
	return 0;
}

测试结果就不贴了吧，有兴趣的朋友可以copy code试一试。

转载请注明原创链接：http://blog.csdn.net/wujunokay/article/details/12113597