计算数组中最大值与最小值的最优方法_寻找最大值的最优算法

主题：

计算数组中最大值与最小值的两种方法

---

内容：

在给定一个数组中同时找到最大值与最小值的计算方法，尽量减小判断次数，提高执行效率。

---

方法一：

思路： 遍历一遍一维数组逐次比较；选择数组中的第一个元素作为最大值与最小值的计算初值，在对数组中元素进行大小判断时，同时只有一种条件成立（即大于或小于），当等于时不需要改变最大或最小值故不作考虑。

代码实现

/**
  * @brief  从指定的缓冲区中找出其中的最大值与最小值
  * @author Mingo
  * @param  array[]: 缓冲区起始位置.
  * @param  size   : 缓冲区大小.
  * @param  *retMax: 返回最大值
  * @param  *retMin: 返回最小值
  * @retval None.
  */
void getMaxAndMin(int array[], int size, int *retMax, int *retMin)
{
    int max,min,n;

    max = array[0];
    min = array[0];
    for (n=1; n<size; n++)
    {
        if (array[n] > max)
        {
            max = array[n];
        }
        else if (array[n] < min)
        {
            min = array[n];
        }
    }
    *retMax = max;
    *retMin = min;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

该方法最好的情况，元素呈递减规律，只要执行第一个判断 < if (array[n] > max) > ，比较次数为：n-1；最坏的情况元素呈递增规律，比较次数为：2*(n-1)。

方法二：

思路： 既然可以遍历数组中的每一个元素，那么我们就可以对数组元素进行分组，然后逐组进行比较。

代码实现

/**
  * @brief  从指定的缓冲区中找出其中的最大值与最小值
  * @author Mingo
  * @param  array[]: 缓冲区起始位置.
  * @param  size   : 缓冲区大小.
  * @param  *retMax: 返回最大值
  * @param  *retMin: 返回最小值
  * @retval None.
  */
void getMaxAndMin(int array[], int size, int *retMax, int *retMin)
{
    int max,min,n;

	if (size == 1)	//判断缓冲区是否只有一个元素
	{
		*retMax = array[0];
    	*retMin = array[0];
		return;
	}
	if (array[0] > array[1])
	{
		max = array[0];
		min = array[1];
	}
	else
	{
		max = array[1];
		min = array[0];
	}
	for(n=2; n < size-1; n+=2)	//size-1: 考虑缓冲区大小的奇偶性
	{
		if (array[n] > array[n+1])
		{
			if (array[n] > max)
			{
				max = array[n];
			}
			if (array[n+1] < min)
			{
				min = array[n+1];
			}
		} 
		else
		{
			if (array[n+1] > max)
			{
				max = array[n+1];
			}
			if (array[n] < min)
			{
				min = array[n];
			}
		}
	}
	if (n != size)	//判断缓冲区大小的奇偶性
	{//缓冲区大小为奇数
		if (array[n] > max)
		{
			max = array[n];
		}
		else if (array[n] < min)
		{
			min = array[n];
		}
	}
    *retMax = max;
    *retMin = min;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68

该方法分两情况：数组元素大小是偶数还是奇数。当在偶数时，先比较两个相连的数组元素，然后再分别对上次的最大与最小值进行比较，每一次循环需要3次比较，一共为：3*(n)/2；当为奇数时，最后剩下的一个元素可能需要1次或许2次，所以总次数为：3*(n)/2+1或3*(n)/2+2。