归并排序用于计算逆序对数
发布时间
阅读量：
阅读量
已知一个整数序列，其长度为n，现要求计算该序列中逆序对的总数。
所谓逆序对，是指在序列中存在两个元素，分别位于第i位和第j位，当i小于j且第i位的数值大于第j位的数值时，这两个元素构成一个逆序对；反之则不构成。
输入描述
第一行给出一个整数n，用于表示序列的长度。
第二行给出n个整数，用以表示完整的序列。
输出描述
请输出一个整数，用以表示所求逆序对的数量。
数据范围说明
1≤n≤100000
输入示例：
6
2 3 4 5 6 1
输出样例：
5
以下为C++语言编写的代码示例：
#include<iostream>
using namespace std;
#define N 100050
int sum = 0;
int tmp[N];
void merge_sort(int q[],int l ,int r)
{
if(l>=r) return;
int mid= l + r >> 1;
merge_sort(q,l,mid);
merge_sort(q,mid+1,r全部评论 (0)
还没有任何评论哟~