C语言程序数组的最大值和最小值的

给出一个大小为N的数组，任务是用最少的比较次数找到数组的最大和最小元素。

示例s:

输入： arr[] = {3, 5, 4, 1, 9}。
输出： 最小的元素是。1
最大的元素是。9

输入： arr[] = {22, 14, 8, 17, 35, 3}
输出： 最小的元素是。3
最大的元素是。35

首先，我们如何从一个函数中返回多个值？我们可以使用结构或指针来实现。
我们创建了一个名为pair的结构（其中包含min和max）来返回多个值。

struct pair {
    int min;
    int max;
};

用线性搜索法计算数组的最大值和最小值

初始化min和max的值，分别为前两个元素的最小值和最大值。从第3个开始，将每个元素与max和min进行比较，并相应地改变max和min（即，如果元素小于min，则改变min，否则如果元素大于max，则改变max，否则忽略该元素）。

下面是上述方法的实现。

/* structure is used to return two values from minMax() */
#include<stdio.h>
struct pair
{
int min;
int max;
};
  
struct pair getMinMax(int arr[], int n)
{
struct pair minmax; 
int i;
  
/*If there is only one element then return it as min and max both*/
if (n == 1)
{
    minmax.max = arr[0];
    minmax.min = arr[0];    
    return minmax;
}
  
/* If there are more than one elements, then initialize min
    and max*/
if (arr[0] > arr[1])
{
    minmax.max = arr[0];
    minmax.min = arr[1];
}
else
{
    minmax.max = arr[1];
    minmax.min = arr[0];
}
  
for (i = 2; i<n; i++)
{
    if (arr[i] > minmax.max)    
    minmax.max = arr[i];
  
    else if (arr[i] < minmax.min)   
    minmax.min = arr[i];
}
  
return minmax;
}
  
/* Driver program to test above function */
int main()
{
int arr[] = {1000, 11, 445, 1, 330, 3000};
int arr_size = 6;
struct pair minmax = getMinMax (arr, arr_size);
printf("nMinimum element is %d", minmax.min);
printf("nMaximum element is %d", minmax.max);
getchar();
}

输出:

Minimum element is 1
Maximum element is 3000

时间复杂度： O(n)
辅助空间： 因为不需要额外的空间，所以是O(1)。

在这种方法中，最坏的情况下比较总数为1+2(n-2)，最好的情况下为1+n – 2。
在上述实现中，最坏的情况发生在元素按降序排序的时候，最好的情况发生在元素按升序排序的时候。

使用锦标赛的方法，实现数组的最大和最小

将数组分成两部分，比较两部分的最大值和最小值，得到整个数组的最大值和最小值。

Pair MaxMin(array, array_size)
如果array_size = 1
返回元素的最大值和最小值
否则，如果arry_size = 2
进行一次比较来确定最大和最小
返回这一对
否则 /* array_size > 2 */
递归左半部分的最大和最小值
循环寻找右半部分的最大和最小值
通过一次比较确定两个候选数的真正最大值
进行一次比较，确定两个候选数的真正最小值
返回一对最大值和最小值

下面是上述方法的实现。

/* structure is used to return two values from minMax() */
#include <stdio.h>
struct pair {
    int min;
    int max;
};
  
struct pair getMinMax(int arr[], int low, int high)
{
    struct pair minmax, mml, mmr;
    int mid;
  
    // If there is only one element
    if (low == high) {
        minmax.max = arr[low];
        minmax.min = arr[low];
        return minmax;
    }
  
    /* If there are two elements */
    if (high == low + 1) {
        if (arr[low] > arr[high]) {
            minmax.max = arr[low];
            minmax.min = arr[high];
        }
        else {
            minmax.max = arr[high];
            minmax.min = arr[low];
        }
        return minmax;
    }
  
    /* If there are more than 2 elements */
    mid = (low + high) / 2;
    mml = getMinMax(arr, low, mid);
    mmr = getMinMax(arr, mid + 1, high);
  
    /* compare minimums of two parts*/
    if (mml.min < mmr.min)
        minmax.min = mml.min;
    else
        minmax.min = mmr.min;
  
    /* compare maximums of two parts*/
    if (mml.max > mmr.max)
        minmax.max = mml.max;
    else
        minmax.max = mmr.max;
  
    return minmax;
}
  
/* Driver program to test above function */
int main()
{
    int arr[] = { 1000, 11, 445, 1, 330, 3000 };
    int arr_size = 6;
    struct pair minmax = getMinMax(arr, 0, arr_size - 1);
    printf("nMinimum element is %d", minmax.min);
    printf("nMaximum element is %d", minmax.max);
    getchar();
}

输出

Minimum element is 1
Maximum element is 3000

时间复杂度： O(n)
辅助空间： O(log n)，因为在递归调用过程中形成的树的最大高度的堆栈空间将被填充，与二叉树相同。

总的比较次数：设比较次数为T(n)。T(n)可以写成如下。
算法范式：分而治之

T(n) = T(floor(n/2)) + T(ceil(n/2)) + 2
T(2) = 1
T(1) = 0

如果n是2的幂，那么我们可以把T(n)写成。

T(n) = 2T(n/2) + 2

在解决了上述递归后，我们得到

T(n)  = 3n/2 -2

因此，如果n是2的幂，该方法会进行3n/2-2的比较，而如果n不是2的幂，则会进行超过3n/2-2的比较。

通过成对比较实现数组的最大和最小

如果n是奇数，那么初始化min和max为第一个元素。
如果n是偶数，则将min和max分别初始化为前两个元素的最小和最大。
对于其余的元素，成对挑选，并分别用最大和最小值比较它们的最大和最小值。

下面是上述方法的实现。

#include<stdio.h>
  
/* structure is used to return two values from minMax() */
struct pair
{
int min;
int max;
};
  
struct pair getMinMax(int arr[], int n)
{
struct pair minmax; 
int i;
  
/* If array has even number of elements then
    initialize the first two elements as minimum and
    maximum */
if (n%2 == 0)
{       
    if (arr[0] > arr[1])    
    {
    minmax.max = arr[0];
    minmax.min = arr[1];
    }
    else
    {
    minmax.min = arr[0];
    minmax.max = arr[1];
    }
    i = 2; /* set the starting index for loop */
}
  
/* If array has odd number of elements then
    initialize the first element as minimum and
    maximum */
else
{
    minmax.min = arr[0];
    minmax.max = arr[0];
    i = 1; /* set the starting index for loop */
}
  
/* In the while loop, pick elements in pair and
    compare the pair with max and min so far */
while (i < n-1)
{       
    if (arr[i] > arr[i+1])      
    {
    if(arr[i] > minmax.max) 
        minmax.max = arr[i];
    if(arr[i+1] < minmax.min)       
        minmax.min = arr[i+1];  
    }
    else        
    {
    if (arr[i+1] > minmax.max)  
        minmax.max = arr[i+1];
    if (arr[i] < minmax.min)        
        minmax.min = arr[i];    
    }   
    i += 2; /* Increment the index by 2 as two
            elements are processed in loop */
}       
  
return minmax;
}
  
/* Driver program to test above function */
int main()
{
int arr[] = {1000, 11, 445, 1, 330, 3000};
int arr_size = 6;
struct pair minmax = getMinMax (arr, arr_size);
printf("nMinimum element is %d", minmax.min);
printf("nMaximum element is %d", minmax.max);
getchar();
}

输出:

Minimum element is 1
Maximum element is 3000

时间复杂度： O(n)
辅助性 因为不需要额外的空间，所以是O(1)。

比较的总数。偶数和奇数的n不同，见下文。

       If n is odd:    3*(n-1)/2  
       If n is even:   1 Initial comparison for initializing min and max, 
                           and 3(n-2)/2 comparisons for rest of the elements  
                      =  1 + 3*(n-2)/2 = 3n/2 -2