利用歸并排序求逆序數(shù)
利用歸并排序求數(shù)列中的逆序數(shù)
逆序數(shù)定義:
一個(gè)數(shù)列中 若i < j,但是a[i]>A[j] , 則a[i]與a[j]就互為逆序數(shù)。
數(shù)組中元素為 9 , 1 , 0 , 5 , 4 則數(shù)組中共有6對逆序數(shù)。分別為(9 , 1) ,(9,0) ,(9,5) ,(9,4),(1,0),(5,4)
解決方法:
改編歸并排序,只需要添加一個(gè)變量 :
當(dāng),a[i]>=a[j] 時(shí),執(zhí)行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 閱讀(2670) 評論(0) 編輯 收藏 引用 所屬分類: 算法相關(guān)

