可以采用以下方法在o(n)时间内选出最大值。
图示：
代码：
int Max(int *A, int arraysize) { int max = A[0], i; for(i=0; i<arraysize; i++) { if(max < A[i]) { max = A[i]; } } return max; }//总共比较 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<stdio.h> #include<stdlib.h> 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<arraysize; i+=2) { if(A[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，如需转载请自行联系原作者
