一、for循环遍历依次查找最大值与最小值
思路:
对于一维数组中的元素,赋max,min的初值为数组的第一个元素,然后将数组中剩余的元素依次和max值最小值比较。
代码:
#include<stdio.h>
void MaxMin(int a[],int n,int &max,int &min){
max=min=a[0];
for(int i=1;i<n;i++){
if(a[i]>max) max=a[i];
else if(a[i]<min) min=a[i];
}
}
int main(){
int a[10]={1,2,45,5,6,12,78,5,6,33};
int max,min;
MaxMin(a,10,max,min);
printf("最大值:%d\n",max);
printf("最小值:%d\n",min);
return 0;
}
分析:该算法的最好、最坏和平均情况下的元素比较次数分别为n-1,2(n-1),3(n-1)/2
该算法的时间最主要花费在元素的比较上。最好情况是a中元素呈现递增排列,元素比较次数为n-1。最坏是元素呈现递减排列,元素比较次数为2(n-1)。对于平均情况,a中有一半的元素比max大,a[i]>max比较执行n-1次,a[i]<min比较执行(n-1)/2次,因此平均元素比较次数为3(n-1)/2
结果:
二、采用递归的思想求一维数组中的max、min
思路:
1、如果数组中的元素只有一个元素则该元素即为max、min
2、如果数组中有两个元素,则比较出max,min
3、如果数组中元素的个数大于两个,则将一维数组分为左右两部分,依次递归,找出左右中的最大值、最小值
代码:
#include<stdio.h>
void MaxMin(int a[],int i ,int j,int &max,int &min){
int mid;
int gmax,gmin,hmax,hmin;
if(i==j) {
max=min=a[0];
return;
}
if(i==j-1){
if(a[i]<a[j]){
max=a[j];
min=a[i];
}
else{
max=a[i];
min=a[j];
}
return;
}
mid=(i+j)/2;
MaxMin(a,i,mid,gmax,gmin);
MaxMin(a,mid+1,j,hmax,hmin);
max=(gmax>hmax?gmax:hmax);
min=(gmin<hmin?gmin:hmin);
}
int main(){
int a[10]={1,2,45,5,6,12,78,5,6,33};
int max,min;
MaxMin(a,0,9,max,min);
printf("最大值:%d\n",max);
printf("最小值:%d\n",min);
return 0;
}
分析:本算法的时间主要花在元素的比较上,设T(n)表示本算法中的比较次数(设n=j-i+1),因此递推式为: T(1)=0; T(2)=1;
当n是2的幂时:T(n)=T(n/2)+T(n/2)+2=…=3n/2-2文章来源:https://www.toymoban.com/news/detail-465976.html
结果:文章来源地址https://www.toymoban.com/news/detail-465976.html
到了这里,关于数据结构:求一维数组中的最大值最小值的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!