利用歸并排序求逆序數

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

逆序數定義：

一個數列中若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) 編輯收藏引用所屬分類: 算法相關

只有注冊用戶登錄后才能發表評論。
【推薦】100%開源！大型工業跨平臺軟件C++源碼提供，建模，組態！

相關文章: 9-24MTK一面二面微軟筆試總結 2011-09-07xx移動創業公司筆試題編程之美2.7 最大公約數 O(n)實現刪除兩個數組中的共同元素編程之美1.9(二) 高效率地安排會面分組背包問題（六）二維背包問題（五）多重背包（三）完全背包問題 <二>

網站導航: 博客園 IT新聞 BlogJava 博問 Chat2DB 管理

jake1036

My Links

Blog Stats

常用鏈接

留言簿(1)

隨筆分類

隨筆檔案

搜索

最新評論

閱讀排行榜

評論排行榜

利用歸并排序求逆序數

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

逆序數定義：

一個數列中若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 。

jake1036

My Links

Blog Stats

常用鏈接

留言簿(1)

隨筆分類

隨筆檔案

搜索

最新評論

閱讀排行榜

評論排行榜

利用歸并排序求逆序數

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

逆序數定義：

一個數列中 若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 。

一個數列中若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)

解決方法：
改編歸并排序，只需要添加一個變量：