void MaxMin(int *values, int n, int &max, int &min)
{
 int  nHalf = n>>1;
 int  i;

 // 通过n/2次交换，使得前半部分总体上小于后半部分，
 // 即最小值肯定在前半部分，最大值肯定在后半部分
 for(i=0; i<nHalf; ++i)
 {
  if(values[i] > values[i+nHalf])
   Swap(values[i], values[i+nHalf]);
 }

 // 如果n为奇数，则最后剩下一个没有比较，
 // 这时让它与第一个比较，如果比第一个更小，则交换，否则不动，作为最大的部分
 if( (n&1) != 0)
 {
  if(values[0] < values[n-1])
   Swap(values[0], values[n-1]);
 }

 // 在前半部分找最小值
 min = values[0];
 for(i=1; i<nHalf; ++i)
 {
  if(values[i] < min)
   min = values[i];
 }

 // 在前半部分找最大值
 max = values[nHalf];
 for(i=nHalf+1; i<n; ++i)
 {
  if(values[i] > max)
   max = values[i];
 }
}

评论