数组是最简单的一种数据结构。我们经常碰到的一个基本问题，就是寻找整个数组中最大的数，或者最小的数。这时，我们都会扫描一遍数组，把最大(最小)的数找出来。如果我们需要同时找出最大和最小的数呢？
对于一个由N个整数组成的数组，需要比较多少次才能把最大和最小的数找出来呢？
本文地址：http://wuyudong.com/2016/07/23/2261.html，转载请注明源地址。
解法一：分别求最大和最小值
可以分别求出数组的最大值和最小值，这样，我们需要比较2N次才能求解。
void find_max_min1(int a[], int size, int *min, int *max)
{
int i;
*min = *max = a[0];
for (i = 1; i < size; i++) {
if (a[i] > *max)
*max = a[i];
if (a[i] < *min)
*min = a[i];
}
}
解法二：分组求解
(1) 按顺序将数组中相邻的两个数分在同一组；
(2) 比较同一组的两个数，将大的数放在偶数位上，小的放在奇数位上；
(3) 最后，从偶数位上求最大值，奇数位上求最小值即可。
一共需要比较1.5N次。这种办法虽然比较次数变少了，但却破坏了原数组。
void swap(int *a, int *b)
{
int p;
p = *a;
*a = *b;
*b = p;
}
void find_max_min2(int a[], int size, int *min, int *max)
{
int i, t;
*min = *max = a[0];
t = (size % 2) ? (size - 2) : (size - 1);
for (i = 0; i <= t; i += 2) {
if (a[i] > a[i + 1])
swap(&a[i], &a[i + 1]);
}
for (i = 0; i <= t; i += 2) {
if (*max < a[i + 1])
*max = a[i + 1];
if (*min > a[i])
*min = a[i];
}
if (size % 2) {
if (*min > a[size - 1])
*min = a[size - 1];
else if (*max < a[size - 1])
*max = a[size - 1];
}
}
解法三：改进的分组
(1) 用两个变量max和min分别存储当前的最大值和最小值。
(2) 同一组的两个数比较完之后，不再调整顺序，将其中较大的与当前max比较，较小的与min比较；
(3) 如此反复，直到遍历完整个数组。
整个过程比较次数为1.5N次。
void find_max_min3(int a[], int size, int *min, int *max)
{
int i, t;
*min = *max = a[0];
t = (size % 2) ? (size - 2) : (size - 1);
for (i = 0; i <= t; i += 2) {
if (a[i] > a[i + 1]) {
if (*min > a[i + 1]) {
*min = a[i + 1];
}
if (*max < a[i]) {
*max = a[i];
}
} else {
if (*min > a[i]) {
*min = a[i];
}
if (*max < a[i + 1]) {
*max = a[i + 1];
}
}
}
if (size % 2) {
if (*min > a[size - 1])
*min = a[size - 1];
else if (*max < a[size - 1])
*max = a[size - 1];
}
}
解法四：分治策略
分别求出前后N/2个数的min和max，然后，取较小的min，较大的max即可。
需要比较的次数为1.5N-2，分析略。
void _find_max_min4(const int arr[], size_t low, size_t high, int *min_value, int *max_value)
{
if (high - low <= 1u) {
if (arr[low] <= arr[high]) {
*min_value = arr[low];
*max_value = arr[high];
} else {
*min_value = arr[high];
*max_value = arr[low];
}
return;
}
size_t mid = low + (high - low) / 2u;
int min_left, max_left;
_find_max_min4(arr, low, mid, &min_left, &max_left);
int min_right, max_right;
_find_max_min4(arr, mid + 1, high, &min_right, &max_right);
*min_value = min_left < min_right ? min_left : min_right;
*max_value = max_left > max_right ? max_left : max_right;
}
void find_max_min4(const int arr[], const size_t len, int *min_value, int *max_value)
{
_find_max_min4(arr, 0, len - 1u, min_value, max_value);
}
Comments