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

算法导论第九章开始的算法同时查找最大值和最小值的算法。

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

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

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

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

//Calculate minimum and maximum at the same time to optimize the algorithm  
#include  
#include  
  
using namespace std;  
  
template  
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  
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




max) max = *(vtI+1);  
        }  
        else  
        {  
            if(*(vtI+1)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 vtd(a, a+18);  
  
    //前  
    for(int j=0; j<18; j++)  
    {  
        cout<

总结：

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