比较3(n-2)/2次数选出最大值和最小值
//第九章例题,以3(n-2)/2次比较同时选择出数组中最大值和最小值 //常规思想是通过两轮比较分别选择出最大值和最小值,优化的方法中采用了只比较一轮, //同时选出两个数先比较一下,将大的与最大值比较,小的与最小值比较 #include<iostream> using namespace std; //判断数组中元素个数是奇数个还是偶数个 bool OddNumber(int n) { if(n%2==0) { return 0; } else return 1; } //循环一遍同时找出最大值和最小值 //如果是奇数个则将第一个元素同时赋给最大值和最小值 //如果是偶数个元素,则将前两个中较大的赋给最大值,较小的赋给最小值 void FindMinAndMax(int a[],int length,int &min,int &max) { int i,little,big; if(length==0) return; //偶数个元素将前两个元素赋给min和max if(!OddNumber(length)) { min=a[0]<a[1]?a[0]:a[1]; max=a[0]>a[1]?a[0]:a[1]; i=2; } //奇数个元素将第一个赋给min和max。 else { min=max=a[0]; i=1; } for(int j=i;j<length-1;j+=2) { little=a[j]<a[j+1]?a[j]:a[j+1]; big=a[j]>a[j+1]?a[j]:a[j+1]; if(min>little) min=little; if(max<big) max=big; } } int main() { int max,min,i; int a[20]; for(i=0;i<20;i++) { a[i]=rand()%100; cout<<a[i]<<" "; } cout<<endl; FindMinAndMax(a,20,min,max); cout<<min<<endl; cout<<max<<endl; return 0; }