首页 > 代码库 > 逆序数(归并排序)
逆序数(归并排序)
在一个排列中，如果一对数的前后位置与大小顺序相反，即前面的数大于后面的数，那么它们就称为一个逆序。一个排列中逆序的总数就称为这个排列的逆序数。
如2 4 3 1中，2 1，4 3，4 1，3 1是逆序，逆序数是4。给出一个整数序列，求该序列的逆序数。
Input
第1行：N，N为序列的长度（n <= 50000)第2 - N + 1行：序列中的元素（0 <= A[i] <= 10^9）
Output
输出逆序数
Input示例
42431
Output示例
4
这题用归并排序做
#include <bits/stdc++.h>using namespace std;const int Maxn = 50010;int A[Maxn];int tmp[Maxn];int cnt = 0;void msort( int* A,int* tmp,int bg,int ed ){ if( ed - bg > 1 ){ int mid = bg + (ed-bg)/2; int x = bg; int y = mid; msort( A,tmp,bg,mid ); msort( A,tmp,mid,ed ); int index = bg; while( x < mid && y < ed ){ if( A[x] > A[y] ){ cnt += mid - x;//如果满足x < y and A[x] > A[y],即逆序,就加(mid-x),因为当前的A[x] > A[y],那么A[x]后面的所有数字都 > A[y], tmp[index++] = A[y++]; }else{ tmp[index++] = A[x++]; } } while( x < mid ){ tmp[index++] = A[x++]; } while( y < ed ){ tmp[index++] = A[y++]; } for( int i = bg; i < ed; i++ ){ A[i] = tmp[i]; } }}int main(){ int n; cin >> n; for( int i = 0; i < n; i++ ){ cin >> A[i]; } msort(A,tmp,0,n); cout << cnt << "\n";}以下是python代码
def sortandcount( alist ): n = len( alist ) count = 0 if n == 2 or n == 1: if n == 2: if alist[0] > alist[1]: alist = alist[::-1] count += 1 return alist,count a,cnt1 = sortandcount( alist[:n/2] ) b,cnt2 = sortandcount( alist[n/2:] ) count += cnt1 + cnt2 resList = [0]*n i = j = 0 len1 = len( a ) len2 = len( b ) for k in range( n ): if i < len1 and j < len2: if a[i] < b[j]: resList[k] = a[i] i += 1 else: resList[k] = b[j] count += len1 - i; j += 1 elif i < len1: resList[k] = a[i] i += 1 else: resList[k] = b[j] j += 1 return resList ,countdef main(): n = input() num = [ input() for i in range(n) ] i,c = sortandcount(num) print cif __name__ == ‘__main__‘: main()
逆序数(归并排序)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。