算法数据结构C++实现7 - 同时查找最大值和最小值优化算法

本算法并不是直接拿数组中的元素来和最大值和最小值比较的，而是先比较数组中两个数组，然后那其中小的和最小值对比，其中大的和最大值对比，那么算法就可以由原来需要对比2n次，降到只需要对比3n/2次了。

对于一个无序查找最小值的算法一般都如下：

 

template<typename T>  
T minimum(vector<T>& vt)  
{  
    T min = vt[0];  
    for(auto x: vt)  
    {  
        if (min >x)  
        min = x;  
    }  
    return min;  
}//The 易做图 way to find a min.  

 

 

这就没什么优化的办法了，但是同时查找最大值和最小值就有办法优化了，程序如下：

 

//Calculate minimum and maximum at the same time to optimize the algorithm  
#include<iostream>  
#include<vector>  
  
using namespace std;  
  
template<typename T>  
void minmaxComp(const T v1, const T v2, T& min, T& max)  
{  
    if(v1<=v2)  
    {  
        min = v1;  
        max = v2;  
    }  
    else  
    {  
        min = v2;  
        max = v1;  
    }  
}//辅助函数  
  
  
template<typename T1, typename T2>  
void myMinMax(typename T1 vt, T2& min, T2& max)  
{  
    //初始化min和max；  
    auto vtI = vt.begin();  
    minmaxComp(*vtI, *(vtI+1), min, max);  
  
    //如果元素为基数，则从第二个值开始  
    if(vt.size()%2 != 0)    vtI++;  
  
    for(; vtI != vt.end(); vtI+=2)  
    {  
        if(*vtI<=*(vtI+1))  
        {  
            if(*vtI<min)     min = *vtI;  
            if(*(vtI+1)>max) max = *(vtI+1);  
        }  
        else  
        {  
            if(*(vtI+1)<min) min = *(vtI+1);  
            if(*vtI>max)     max = *vtI;  
        }  
    }  
}//at most 3(n/2) comparisons  
  
  
void test()  
{  
    //初始化数组  
    double a[18] =   
    {32., 12., 0.7, 5., 0.1, 0.7, 0.8,0.7, 99., 0.4, 1., 2.5, 3.6, 5., 9., 12., 19.,23.};  
    vector<double> vtd(a, a+18);  
  
    //前  
    for(int j=0; j<18; j++)  
    {  
        cout<<a[j]<<" ";  
    }  
    cout<<endl<<endl;  
  
    double myMin = 0;  
    double myMax = 0;  
  
    //调用函数  
    myMinMax(vtd, myMin, myMax);      
      
    //后  
    cout<<"Minimum is: "<<myMin<<"\nMaximum is: "<<myMax<<endl;  
}  
  
int main()  
{  
    test();  
    return 0;  
}  

 

 

总结：

本算法还是挺巧妙的，算是introduction to algorithm 中比较容易的算法了。

补充：软件开发 , C++ ,