算法导论第九章例题之寻找最大数和最小数优化版

该算法为寻找最大值和最小值的优化版，普通的方法需要比较3（n-2）/2次，而优化之后的算法只需要比较2lgn-n/2次。

思路为：将数组中元素两两比较，大的放到big数组中，小的放到small数组中，对big数组中的数字两两比较，去掉小的，保留大的，直到只剩一个元素为止。该元素即为最大值。

求最小值的思路同最大值。

具体思路见代码：

//优化算法
//第九章例题，以2lgn-n/2的比较次数同时选择出数组中最大值和最小值，比较次数比3（n-2）/2少
//算法思路是每两个元素进行比较，将所有较小的元素取出放到一个数组，最小的元素肯定在这里面，
//再将这两个数组中每两个元素进行比较，丢弃较大的元素，依次类推直到剩下一个元素为止，此元素即为最小的元素
//同理，最大元素寻找的方法也是这样
#include<iostream>
using namespace std;
void FindMinAndMax(int a[],int length,int &min,int &max)
{
	int small[10],big[10];
	int i,j=0,k=0,s,b,lengths,lengthb;
	//将数组进行分组，每两个元素比较，较大的放到big数组中
	//较小的放到small数组中
	for(i=0;i<length-1;i+=2)
	{
		if(a[i]<a[i+1])
		{
			s=a[i];
			b=a[i+1];
		}
		else
		{
			s=a[i+1];
			b=a[i];
		}
		small[j++]=s;
		big[k++]=b;
	}
	if(length%2==1)
	{
		small[j++]=a[length-1];
		big[k++]=a[length-1];
	}
	//获取small数组和big数组的长度
	lengths=j;
	lengthb=k;
	//每两个元素进行比较，将较小的保留较大的去掉
	//知道数组中只剩一个元素，此元素即为最小元素
	while(lengths>1)
	{
		j=0;
		for(i=0;i<lengths-1;i+=2)
		{
			if(small[i]<small[i+1])
			{
				small[j++]=small[i];
			}
			else
			{
				small[j++]=small[i+1];
			}
		}
		//如果元素个数为奇数个，则最后一个元素没法进行比较，则直接放到下一轮
		if(lengths%2==1)
		{
			small[j++]=small[lengths-1];
		}
		lengths=j;
	}
	//保留的最后一个元素即为最小的元素
	min=small[0];
	//同理可得最大元素
	while(lengthb>1)
	{
		j=0;
		for(i=0;i<lengthb-1;i+=2)
		{
			if(big[i]>big[i+1])
			{
				big[j++]=big[i];
			}
			else
			{
				big[j++]=big[i+1];
			}
		}
		if(lengthb%2==1)
		{
			big[j++]=big[lengthb-1];
		}
		lengthb=j;
	}
	max=big[0];
}
int main()
{
	int a[9]={2,5,4,6,3,1,7,8,9};
	int min,max;
	FindMinAndMax(a,9,min,max);
	cout<<min<<endl;
	cout<<max<<endl;
	return 0;
}