求数组最大的前两个数，要求比较次数尽可能少

1. 从一个数组中找到最大的前两个数*，x1 >= x2，要求比较次数尽可能少

• 最简单直接的方法就是 从前到后，逐一比较，第一轮找到最大的，第二轮找到次大的，这样的需要大约比较：2n 次

• 设定两个变量，一个变量x1存储最大值，另外一个变量x2存储次大值；即x1 >= x2; 因此每次在比较时，先比较与x2的大小，当且仅当大于x2后才比较与x1的大小；

#include<iostream>
using namespace std;

void fun(int a[],int lo, int hi, int &x1, int &x2)
{
    if(a[x1=lo]<a[x2=lo+1])
    {
        int temp=x1;
        x1 = x2;
        x2 = temp;
    }
    for(int i=lo+2; i < hi; ++i)
    {
        if(a[i]>a[x2])
        {
            if(a[x2=i]>a[x1])
            {
                int temp=x1;
                x1 = x2;
                x2 = temp;
            }
        }
    }
}

int main()
{
    int a[]={1,2,3,4,5,6,10,9,8,7};
    int x1=0,x2=0;
    fun(a,0,10,x1,x2);
    cout<<a[x1]<<a[x2];
}

此时，最好的情况，即只需要最外面一层比较，即数组是逆序（大->小）的，需要 n 次比较；最坏的情况，即需要两层比较，即数组是顺序的（小->大），需要 2n 次比较；

分治 + 递归

将数组分为左右两部分，找出左边的最大值和次大值；再找出右边的最大值和次大值；然后把这四个值进行比较；再对左边数组和右边数组递归；
递归基：
因为要取最大值和次大值，因此至少要有2个数；剩下2个数时，取最大值和次大值；剩下3个值时，不能再分为左右两边（一边2个，一边1个，不符合比较），因此三个值也要直接返回，取最大值和次大值；剩下4个值时，可分为左右2个，再往上也都可以合理分为左右2边；

void fun2(int a[], int lo, int hi, int &x1, int &x2)
{
    if(lo+2 == hi)
    {
        if(a[x1 = lo] < a[x2 = (lo+1)])
        {
            x1 = lo + 1;
            x2 = lo;
        }
        return;
    }

    if(lo+3 == hi)
    {
        if(a[lo]>a[lo+1])
        {
            if(a[lo]>a[lo+2])
            {
                x1 = lo;
                x2 = (a[lo+1]>a[lo+2]?(lo+1):(lo+2));
            }
            else
            {
                x1 = lo + 2;
                x2 = lo;
            }
        }
        else
        {
            if(a[lo+1]<a[lo+2])
            {
                x1 = lo+2;
                x2 = lo+1;
            }
            else
            {
                x1 = lo+1;
                x2 = a[lo]>a[lo+2]?lo:(lo+2);
            }
        }
        return;
    }

    int mi = (lo+hi)/2;

    int x1L, x2L;
    fun2(a, lo, mi, x1L, x2L);

    int x1R, x2R;
    fun2(a, mi, hi, x1R, x2R);

    if(a[x1 = x1L] < a[x2 = x1R])
    {
        x1 = x1R;
        x2 = x1L;
        if(a[x1L]<a[x2R])
        {
            x2 = x2R;
        }
    }
}

扩展：如何快速求百万级数据的前TopK，待续