【问题描述】

给定数组a[0:n-1]，使设计一个算法，在最坏情况下用「3/n-2」次比较找出a[0:n-1]中元素的最大值和最小值。（《计算机算法设计与分析》，王晓东，2—15）

【算法设计】

1      5      8     2     3      9

   5             8           9

          8            9

                9

求最小值设计与此类似，在此未画出图示。

【算法实现】

void SelectMaxAndMin(int *a,int *b,int n)

{

       int j=1,s=1,i=1;

       if(n==1)  return;

       for(i=1;i<n;i=i+2)

       {

        if(a[i]<a[i+1])

               a[j++]=a[i+1];

        else

               a[j++]=a[i];

        if(b[i]<b[i+1])

               b[s++]=b[i];

        else

               b[s++]=b[i+1];

       }

       if(i==n)

       {

              a[j]=a[n];

        b[s]=b[n];

       }  

       SelectMaxAndMin(a,b,(n+1)/2);

}

【测试程序】

void main()

{

       int n,k,*a,*b;

       cout<<"请输入数组的大小："<<endl;

       cin>>n;

       a=new int[n+1];

       b=new int[n+1];

       a[0]=0;

       cout<<"请输入数组："<<endl;

       for(k=1;k<=n;k++)

              cin>>a[k];

       for(k=0;k<=n;k++)

       {               

        b[k]=a[k];

       }

       SelectMaxAndMin(a,b,n);     

    cout<<"该组数据最大值和最小值分别为："<<endl;

    cout<<a[1]<<endl;

       cout<<b[1]<<endl;

}

评论