工学1号馆

home

寻找数组中的最大值与最小值

Wu Yudong    July 23, 2016     Algorithm   724

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) 最后，从偶数位上求最大值，奇数位上求最小值即可。

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) 如此反复，直到遍历完整个数组。

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];
}
}

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);
}