利用歸并排序求逆序數

                       利用歸并排序求數列中的逆序數

 逆序數定義：

    一個數列中 若i < j,但是a[i]>A[j] ,  則a[i]與a[j]就互為逆序數。

    數組中元素為 9 , 1 , 0 , 5 , 4 則數組中共有6對逆序數。分別為(9 , 1) ，(9，0) ，(9，5) ，(9，4)，(1，0)，(5，4) 
  
 解決方法：
   改編歸并排序，只需要添加一個變量 ：

    當，a[i]>=a[j] 時，執行count += mid - i + 1 。

   代碼如下：

  

#include <iostream>
using namespace std ;

 void mergeSort(__int64 * a , int p , int q , __int64 &count) ;
 void merge(__int64* a , int p , int mid , int q ,__int64 & count)  ;
 __int64 L[500000] , R[500000] ;
  int main()
  {
    __int64 a[500000] ;
    int n ;
    cin>>n;
    
    while(n > 0)
    {  
    
      __int64 count  = 0 ;
      for(int i = 0 ; i < n ; i++)
         cin>>a[i] ;
      
      mergeSort(a , 0 , n - 1 , count) ;
      
      cout<<count<<endl; 
      cin>>n ;
    }
     
    return 0 ;  
  }
  
   void mergeSort(__int64 * a , int p , int q , __int64 & count) 
   {
     if(p < q)
     {
       int mid = (p + q) / 2;
       
       mergeSort(a , p , mid , count) ;
       mergeSort(a , mid + 1 , q , count) ;
       merge(a , p , mid , q , count) ;   
     }         
   }
  
  void merge(__int64 * a , int p , int mid , int q , __int64 & count) 
  {
      
     // int * L = new int[mid - p + 1 ] ;
    //  int * R = new int[q - mid ] ;
      int i , j ;
      for(i = p ; i <= mid ; i++)
       L[i] = a[i] ;
       
      for(j = mid + 1 ; j <= q ; j++)
       R[j] = a[j] ;
       
       i = p ;
       j = mid + 1 ;   
      int w = p ;
      while(i <= mid && j <= q)
      {
         if(L[i] <= R[j])
         {
           a[w++] = L[i++] ;      
            
         }
         else
         {
           count +=  mid - i + 1 ;     //注意此處的處理 
           a[w++] = R[j++] ;
         }                 
           
      } 
      
      
       while(i <= mid)
        {
            a[w++] = L[i++] ;           
        }
       
       while(j <= q)
       {
          a[w++] = R[j++] ;            
       }
       
       
    //   delete [] L ;
    //   delete [] R ;
       
  }

posted on 2011-04-06 15:55 kahn 閱讀(2657) 評論(0)  編輯 收藏 引用 所屬分類: 算法相關