算法导论第九章中位数和顺序统计学例题

比较3（n-2）/2次数选出最大值和最小值

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