选最大与最小（分治法）

struct Max_Min{//max & min和与之对应的下标值
    int max_i, min_i;
};
/*思路：
 *  将数组均分为两个，分别找到两个数组中的最大值与最小值。递归分治。
 * 再比较这两个数组分别得到的最大值得出最大值，最小值同理。
 */ 
Max_Min Find_Max_and_Min(int *array, int begin, int end)
{
    int n = end - begin + 1;
    if(n == 1){
        Max_Min max_min;
        max_min.max_i = max_min.min_i = begin;      
        return max_min;
    }
    if(n == 2){
        Max_Min max_min;
        if(array[begin] >= array[end]){
            max_min.max_i = begin;
            max_min.min_i = end;
        }
        else{
            max_min.max_i = end;
            max_min.min_i = begin;
        }
        return max_min;
    }
    else if(n % 2){//奇
        int temp = (n - 1) / 2;
        Max_Min max_min, max_min1, max_min2;
        max_min1 = Find_Max_and_Min(array, begin, begin + temp - 1);
        max_min2 = Find_Max_and_Min(array, begin + temp, end - 1);
        //存在1轮空元素
        //比较大小
        if(array[max_min1.max_i] >= array[max_min2.max_i]){
            if(array[max_min1.max_i] >= array[end])
                max_min.max_i = max_min1.max_i;
            else
                max_min.max_i = end;
        }
        else{
            if(array[max_min2.max_i] >= array[end])
                max_min.max_i = max_min2.max_i;
            else
                max_min.max_i = end;
        }
        if(array[max_min1.min_i] < array[max_min2.min_i]){
            if(array[max_min1.min_i] < array[end])
                max_min.min_i = max_min1.min_i;
            else
                max_min.min_i = end;
        }
        else{
            if(array[max_min2.min_i] < array[end])
                max_min.min_i = max_min2.min_i;
            else
                max_min.min_i = end;
        }
        return max_min;
    }
    else{//偶
        Max_Min max_min, max_min1, max_min2;
        max_min1 = Find_Max_and_Min(array, begin, begin + n / 2 - 1);
        max_min2 = Find_Max_and_Min(array, begin + n / 2, end);
        //比较大小
        if(array[max_min1.max_i] >= array[max_min2.max_i])
            max_min.max_i = max_min1.max_i;
        else
            max_min.max_i = max_min2.max_i;
        if(array[max_min1.min_i] < array[max_min2.min_i])
            max_min.min_i = max_min1.min_i;
        else
            max_min.min_i = max_min2.min_i;
        return max_min;
    }
}

原理参见 屈婉玲老师 算法设计与分析 ORZ