设计一个c语言程序,用最少的比较次数,搜索整型数组中的最大和最小数

Question

如题所述

Answer 1

可以看到这个问题他们其他人的程序共有n-1趟循环，每趟循环进行2次比较，共有2*n - 2次比较。如果从尽可能减少比较操作次数来提高性能的角度出发，他们的程序并不是最优的，其实对n个数的数列，同时找出他们的最小值和最大值，最少的比较次数可做到3 * n / 2，这个次数是小于2*n-2的。算法的思路是: 将该列数每相邻两个分成一组，得出每组的较大者和较小者，这里进行了n / 2次比较，然后把各组的较大者放在一块找出它们的最大者即可得到全体中的最大元，这里将有(n / 2) - 1次比较(因为共分成n / 2组，因此是在n/2个数中选出最大值，所以需要n/2-1次比较)，同理在n/2个较小者中选出最小值需要n/2-1次比较。所以这种算法大约需要3*n/2次比较，算比较快的了。实现时，将每相邻的两个元素分成一组，然后一组一组处理，例如下标为0的与下标为1为第1组，下标为2的与下标为3的为第2组，...下标为2i与下标为2i+1的为第i组，Max用于存储前i组中已决出的最大元，Min用于存储前i组中已决出的最小元，max用于表示第i组中的较大元，min表示第i组中的较小元，在处理第i组前，Max为前2(i - 1)个元素中的最大元，Min为前2(i - 1)个元素中的最小元，则处理第i组时，先比较a[2*i]与a[2*i+1]，较大者为max，较小者为min，然后再将Max与max比较，其中较大的为前2i个元素中的最大者，再将Min与min比较，较小的即为前2i个元素中的最小者，当i为第n/2组时（即最后一组）结束：
bool find_MinMax(int a[], int n, int &Max, int &Min) { //从n个数中找出最大值Max与最小值Min
int max, min, i;
if(n < 1) return false; /*如果是空列，则返回失败*/
if(n == 1){ /*如果只有一个元素，则这个元素既是最大元又是最小元*/
Max = a[0], Min = a[0];
return true;
}
if(a[0] > a[1]) { /*先假定a[0]与a[1]中的较大元为最大元、较小元为最小元*/
Max = a[0], Min = a[1];
}
else {
Max = a[1], Min = a[0];
}
for(i = 1; 2 * i < n - 1; i++) {/*然后每两个为一组进行处理*/
if(a[2 * i] > a[2 * i + 1]) {
max = 2 * i, min = 2 * i + 1;
}
else {
max = 2 * i + 1, min = 2 * i;
}
if(a[max] > Max) Max = a[max];
if(a[min] < Min) Min = a[min];
}
if(n % 2) { //如果元素总个数为奇数，则处理最后的这个落单的元素
if(a[n - 1] > Max) Max = a[n - 1];
else if(a[n - 1] < Min) Min = a[n - 1];
}
return true;
}

Answer 2

int arr[6]={2,3,45,6,78};
int max=arr[0];
int min=arr[0];
for(int i=0;i<6;i++)
{
if(max<arr[i])max=arr[i];

if(min>arr[i])min=arr[i];
}
printf......
更多交流参考我空间文章。

Answer 3

如果数组中的值没有规律，这个恐怕没有太好的办法，只有从头到尾比较一遍。
int max = a[0];
int min = a[0];
for( i = 1; i < N; ++i )
{
int tmp = a[i];
if ( tmp > max ){ max = tmp; }
if ( tmp < min ){ min = tmp; }
}本回答被网友采纳