jake1036

利用归并排序求逆序数

                       利用归并排序求数列中的逆序数

 逆序数定义：

    一个数列中 若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 阅读(2639) 评论(0)  编辑 收藏 引用 所属分类: 算法相关


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   博问   Chat2DB   管理