中位数和顺序统计学

                  中位数和顺序统计学

1 求最大和最小值

 
  求取最大和最小值，方法是成对的比较元素，两个元素之间较大值与max比较，较小值与min比较，这样每两个数字需要进行
  3次比较，总共就进行了3[n/2]次比较。
  
  若n为奇数，则min和max同时赋值为数组中的第一个元素
  若n为偶数，则数组中的前两个元素，首先进行比较，分别赋值给min和max，然后剩余的元素逐对比较
   代码如下：
 

/**//*
  求取最大和最小值，方法是成对的比较元素，两个元素之间较大值与max比较，较小值与min比较，这样每两个数字需要进行
  3次比较，总共就进行了3[n/2]次比较。
   
  若n为奇数，则min和max同时赋值为数组中的第一个元素 
  若n为偶数，则数组中的前两个元素，首先进行比较，分别赋值给min和max，然后剩余的元素逐对比较、 
*/

#include <iostream>
using namespace std ;
  void minMax(const int * a , const int n , int & min , int &max) ; 
  inline int  MIN(int x , int y) { return (x <= y) ? x : y ;};
  inline int  MAX(int x , int y) { return (x <=y ) ? y : x ;} ;
  void find(const int * a , int begin ,const int n , int & min ,int & max);
  int main()
  {
    int a [] = {23 , 1 , -1 , 55 , 34 ,2 , -90 , 43 , -100} ;
    
    int min = 0 ;
    int max = 0 ;
    minMax(a , 9 ,min , max);
    cout<<"min: "<<min<<"max: "<<max<<endl ;
    cin.get() ;
    return 0 ;    
  }
  

  void minMax(const int * a , const int n , int & min , int & max)
  {
    if(n < 1)  //小于1 表示错误 
    {
     return ;     
    }   
    if(n == 1)//等于1 表示则直接返回结果 
    {
      min = max = a[0] ;
      return ;     
    }   
       
    if((n & 1) == 1)  //n为奇数
    {
      min = max = a[0] ;//同时赋值给第一个元素      
     find(a , 1 , n , min , max);
    } 
    else             //n为偶数 
    {
     min = MIN(a[0] , a[1]) ;
     max = MAX(a[0] , a[1]) ;
     find(a , 2 , n , min , max);  
          
    }
    
       
  }
  
  //每两个元素逐对比较 
  void find(const int * a , int begin ,const  int n , int & min ,int & max)
  {      
         for(int i = begin ; i < n - 1 ;i++ )
         {
           int minTemp =  MIN(a[i] , a[i + 1]) ;
           int maxTemp =  MAX(a[i] , a[i + 1]) ;                 
           if(min > minTemp)
           {
             min = minTemp ;
           }
           if(max < maxTemp) 
           {
             max = maxTemp ;      
           }               
         }           
  }
  

 2   利用分治法求取数组中任意的第i大数

      随机选择第i大数字，借助于快排函数的partition()函数，将数组分成两个部分，则第i大数字必然在这两个部分之中的一个。
  利用分治法进一步划分该问题。

/**//*
  随机选择第i大数字，借助于快排函数的partition()函数，将
  数组分成两个部分，则第i大数字必然在这两个部分之中的一个。
  利用分治法进一步划分该问题。 

*/
#include <iostream>
using namespace std ;

  int partition(int * a , int p , int q)
  {
    int i = p -1 , x = a[q] ;
    
  for(int j = p ; j < q ; j++)
   { 
    if( a[j] <= x )
    {
      i++ ;
      swap(a[i] , a[j]) ;        
    }
  } 
    swap(a[i + 1] , a[q]) ;    
    return i + 1 ;
  }
   
  int  select(int * a , int p , int i , int r)
  {
     if(p == r)
       return a[p] ;
         
     
        int q = partition(a , p , r) ;                 
        int w = q - p + 1 ; //表示第一个区间中数字的个数       
        if(w == i) //此处切记 i 不能与 q 进行比较 ，q仅仅返回数组中的下标 
         return a[q] ;    
        if(i < w) //表示在第一个区间中 
         return select(a , p ,  i , q - 1) ;
        else
         return select(a , q + 1 ,  i - w , r) ; 
                             
  }
  

  int main()
  {
   int a [] = {12 , 4 , 23 , 5 ,7 , 2 ,11} ;//2 , 4 , 5 ,7 ,11 , 12 , 23
   int res = select(a , 0 ,4 ,6) ;
   cout<<"res:"<<res; 
    cin.get();
    return 0 ;    
  }

posted on 2011-04-06 15:37 kahn 阅读(569) 评论(0)  编辑 收藏 引用 所属分类: 算法相关