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 阅读(2280) 评论(0)  编辑 收藏 引用 所属分类: 算法相关


只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理