同时找出最大值和最小值的一种优化算法-MaxAndMin
在一个有n个元素的集合中，单独求出最大值（或最小值）的算法，很容易实现，只需按序扫描整个序列，记录最大值（或最小值），其上限为n-1次。
但在很多应用中，需同时找到最大值和最小值，一般情况大家较容易想到用上面的算法独立的找到最大值和最小值，各用n-1次，共有2n-2次比较。这在大容量数据库中（n很大），效率不是很高。
在这里，我将给出一种新的算法代码，以大幅提高其效率（n很大时）。具体做法是：每次成对的处理数据，先将一对元素进行比较，然后把较大者与当前最大值比较，较小者与当前最小者比较，因此每两个元素需要3次比较。具体实现时需考虑n的奇偶，n为奇数，3【n/2】次；n为偶数，3n/2-2次。因此总的比较次数至多为3【n-2】。（注：【n】表示不大于n的整数）。
具体C++源代码如下：
#include <iostream.h>
#include <limits.h> //包含INT_MAX，INT_MIN的头文件
int nMax = INT_MIN; //将INT_MIN设为当前最大值的初始值
int nMin = INT_MAX;
/**//////记录比较最大值函数int Max(int nNum)
{
if (nMax<nNum)
{
nMax = nNum;
}
return nMax;
}
/**//////记录比较最小值函数int Min(int nNum)
{
if (nMin>nNum)
{
nMin = nNum;
}
return nMin;
}
void main()
{
//测试序列
int nData[] = {3,2,5,9,4,2,1,13,0,-1,1380};
int nLen = sizeof(nData)/sizeof(nData[0]);
if (nLen%2 == 1) //待测数据为奇数
{
//待测数据为奇数，最值初始值均设为nData[0]
Max(nData[0]);
Min(nData[0]);
for (int i=1;i<=(nLen-1)/2;i++)
{
if (nData[i]>nData[nLen-i])
{
Max(nData[i]);
Min(nData[nLen-i]);
}
else
{
Max(nData[nLen-i]);
Min(nData[i]);
}
}
}
else //待测序列为偶数
{
for (int i=0;i<nLen/2;i++)
{
if (nData[i]>nData[nLen-i-1])
{
Max(nData[i]);
Min(nData[nLen-i-1]);
}
else
{
Max(nData[nLen-i-1]);
Min(nData[i]);
}
}
}
cout<<"nMax = "<<nMax<<endl<<"nMin = "<<nMin<<endl;
}posted on 2012-05-14 12:39
代码之美 阅读(6496)
评论(2) 编辑 收藏 引用