中位數和順序統計學

                  中位數和順序統計學

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 閱讀(541) 評論(0)  編輯 收藏 引用 所屬分類: 算法相關