计算最大值和最小值（分治法）

分治法计算最大值和最小值，是一个经典的算法程序。

原始数据使用随机函数生成。

采用结构化程序设计，可以很容易改为从标准输入或文件读入数据，只需要修改函数getData即可。

数据个数由宏定义给出，也可以轻松地改为输入。

/*
 * 求最大和最小值
 * 这里包括经典的算法和分治算法的实现
 */

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define N 7

void getData(int [], int);
void outputData(int [], int);

void maxmin1(int [], int);
void maxmin2(int [], int, int, int *, int *);

int max, min;

int main(void)
{
    int a[N];

    getData(a, N);
    outputData(a, N);

    maxmin1(a, N);
    printf("max=%d min=%d
", max, min);

    maxmin2(a, 0, N-1, &max, &min);
    printf("max=%d min=%d
", max, min);

    return 0;
}

/* 经典计算最大值和最小值的算法程序 */
void maxmin1(int d[], int n)
{
    int i;

    max = min = d[0];
    for(i=1; i<n; i++) {
        if(d[i] > max)
            max = d[i];
        else if(d[i] < min)
            min = d[i];
    }
}

/* 分治法计算最大值和最小值的算法程序，递归实现 */
void maxmin2(int d[], int left, int right, int *max, int *min)
{
    int max1, min1;

    if(left==right) {
        *max = d[left];
        *min = d[left];
    } else if(left == right-1) {
        if(d[left] > d[right]){
            *max = d[left];
            *min = d[right];
        } else {
            *max = d[right];
            *min = d[left];
        }
    } else {
        int mid = (left + right) / 2;
        maxmin2(d, left, mid, max, min);
        maxmin2(d, mid+1, right, &max1, &min1);
        if(*max < max1)
            *max = max1;
        if(*min > min1)
            *min = min1;
    }
}

void getData(int d[], int n)
{
    time_t t;
    srand((unsigned) time(&t));  /* 设置随机数起始值 */

    int i;
    for(i=0; i < n; i++)
        d[i] = rand() % 1000; /* 获得0-999之间的整数值 */
}

void outputData(int d[], int n)
{
    int i;
    for (i = 0; i < n; i++)
      printf("%d ", d[i]);
    printf("
");
}

核心代码：

/* 分治法计算最大值和最小值的算法程序，递归实现 */
void maxmin2(int d[], int left, int right, int *max, int *min)
{
    int max1, min1;

    if(left==right) {
        *max = d[left];
        *min = d[left];
    } else if(left == right-1) {
        if(d[left] > d[right]){
            *max = d[left];
            *min = d[right];
        } else {
            *max = d[right];
            *min = d[left];
        }
    } else {
        int mid = (left + right) / 2;
        maxmin2(d, left, mid, max, min);
        maxmin2(d, mid+1, right, &max1, &min1);
        if(*max < max1)
            *max = max1;
        if(*min > min1)
            *min = min1;
    }
}