22

同时找出最大值和最小值的一种优化算法-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的头文件



intnMax=INT_MIN;//将INT_MIN设为当前最大值的初始值

intnMin=INT_MAX;

///////记录比较最大值函数

intMax(intnNum)

{

if(nMax<nNum)

{

nMax=nNum;

}

returnnMax;

}

///////记录比较最小值函数

intMin(intnNum)

{

if(nMin>nNum)

{

nMin=nNum;

}

returnnMin;

}

voidmain()

{

//测试序列

intnData[]={3,2,5,9,4,2,1,13,0,-1,1380};

intnLen=sizeof(nData)/sizeof(nData[0]);



if(nLen%2==1)//待测数据为奇数

{

//待测数据为奇数，最值初始值均设为nData[0]

Max(nData[0]);

Min(nData[0]);



for(inti=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(inti=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;

}原文链接: https://www.cnblogs.com/huawei198707/archive/2012/05/18/2508263.html

欢迎关注

微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍