[转载]一组数中找max或min的最快方法是什么?

最坏的情况是a中的元素递减排序,这时要比较的次数为2(n-1);
最好的情况是a中的元素递增排序,这时要比较的次数为(n-1);

所以平均比较次数为:
(2(n-1)+(n-1))/2 = 3n/2-3/2<=3n/2
这应该是对无序数组查找最大最小值的最好方法了,该算法的平均比较次数不多于3n/2;

void maxmin(int a[], int n){
int i,max,min;

max=a[0];
min=a[0];
for (i=1;i<n;++i){
if (a[i]>max)
max = a[i];
else if(a[i]<min)
min = a[i];
}
}

 

原文地址http://bbs.chinaunix.net/viewthread.php?tid=921358

此条目发表在Program分类目录。将固定链接加入收藏夹。

发表评论

电子邮件地址不会被公开。 必填项已用*标注

您可以使用这些HTML标签和属性: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>