最大值和最小值-白红宇

可以采用以下方法在o(n)时间内选出最大值。

图示：

代码：

int Max(int *A, int arraysize){        int max = A[0], i;        for(i=0; i

//总共比较 n-1 次

现在有两个问题：

1）如何同时找到最大值和最小值

　　2）如何找到最大的两个值

解决方案：

问题1）

　　方案一：可以采用像找最大值Max()函数解决。这样总共执行2(n-1)次

　　方案二：一次处理两个元素，如下图所示：

　　　分析：

当数组元素总个数arraysize为奇数时，max和min同时赋值为第一个元素，之后的元素每两个比较一次之后大的和大的比，小的和小的比，总共比较（n-1）*3/2次。

　当arraysize为偶数时，头两个元素先比较一下，大的赋值给max,小的赋值给min，之后和上述一样，两个两个的处理。总共比较（n-2）*3/2+1次

显然2*n > 3/2 *n，所以方案二是一种更快的算法。

#include
     
      #include
      
       int main(){        int max, min, i;        int A[] = {
   0, 2, 55, 3, 5, 2, 9};        int arraysize = 7;        if(arraysize % 2 == 0)        {            if(A[0] > A[1])            {                max = A[0];                min = A[1];            }            else            {                max = A[1];                min = A[0];            }            i = 2;        }        else        {            max = min = A[0];            i = 1;        }        for(; i
       
         A[i+1])            {                if(A[i] > max)                {                    max = A[i];                }                if(A[i+1] <  min)                {                    min = A[i+1];                }            }            else            {                if(A[i+1] > max)                {                    max = A[i+1];                }                if(A[i] < min)                {                    min = A[i];                }            }        }        printf("max:%d\nmin:%d\n", max, min);        return 0;}

问题2）

　　和问题1方案二一样，两个两个的处理。两个比较后大的和最大值比较，小的和次大值比较，如果大的就取代之。

本文转自jihite博客园博客，原文链接：http://www.cnblogs.com/kaituorensheng/archive/2013/03/03/2941951.html，如需转载请自行联系原作者