面试题--尽可能的减少求一个数组的最大最小值的比较次数

最普通的思路是2*N次的比较。

那么如何优化呢：

参考http://www.cnblogs.com/bestDavid/p/ExaminationALBABA.html

3、设计一个最优算法来查找一n个元素数组中的最大值和最小值。已知一种需要比较2n次的方法，请给一个更优的算法。情特别注意优化时间复杂度的常数。

解：把数组两两一对分组，如果数组元素个数为奇数，就最后单独分一个，然后分别对每一组的两个数比较，把小的放在左边，大的放在右边，这样遍历下来，总共比较的次数是 N/2 次；在前面分组的基础上，那么可以得到结论，最小值一定在每一组的左边部分找，最大值一定在数组的右边部分找，最大值和最小值的查找分别需要比较N/2 次和N/2 次；这样就可以找到最大值和最小值了，比较的次数为

　　　　　　N/2 * 3 = (3N)/2 次

如图会更加清晰：

代码实现：

#include <stdio.h>
#include <stdlib.h>
#define N 8
int main(void)
{
    //int arr[N] = {4, 1, 5, 9, 9, 7, 10};
    int arr[N] = {1,2,3,4,5,6,9,1};
    int iter = 0;
    int cnt = 0;
    for(iter = 0; iter < N ; iter += 2)
    {
        if(++cnt && arr[iter] > arr[iter + 1] )
        {
            int temp = arr[iter];
            arr[iter] = arr[iter + 1];
            arr[iter + 1] = temp;
        }
    }
    int i = 0;
    for(i = 0; i < N; i++)
    {
        printf("%-3d", arr[i]);
    }
    printf("
");
    int myMin = arr[0];
    for(iter = 2; iter < N ; iter += 2)
    {
        if(++cnt && arr[iter] < myMin)
        {
            myMin = arr[iter];
        }
    }
    int myMax = arr[1];
    for(iter = 3; iter < N; iter += 2)
    {
        if(++cnt && arr[iter] > myMax)
        {
            myMax = arr[iter];
        }
    }
    if(N % 2 != 0 && ++cnt && myMax < arr[N - 1]) myMax = arr[N - 1];
    printf("min is %d
", myMin);
    printf("max is %d
", myMax);
    printf("compare times is %d", cnt);
    return 0;
}

　　上面的算法比较次数基本上已经是最优了，但是有朋友提出这样的顾虑，在极端的情况下，每次都做交换，可能会导致程序开销很大，这样的顾虑是对的，其实在上面的算法的基础上，可以不做交换就能找到最大值和最小值。

第3题改进的算法：

　　依旧把数组两两一组分配，不做交换操作，设置一个最大值Max和最小值Min，依次和每一组的两个数据做比较，把较大的值给Max,较小的值给Min，遍历一次就能找到数组的最大值和最小值。

　　示例：数组为{(4, 1) , (5, 9) , (9 ,7) ,(10,2)},经过第一组比较得到Max = 4，Min = 1，其中比较了3次；,经过第二组比较得到Max = 9，Min = 1，其中比较了3次；……到最后Max = 10，Min = 1；比较次数是3 * N/2 = (3N)/2，比较次数没有改变！代码实现不难，就不贴了