题意是要求排序交换的次数，因为数据较大，冒泡肯定超时，快排又没办法得到交换次数，所以用复杂度相同的归并排序，这里有一个逆序对的概念：
对于一个包含N个非负整数的数组A[1..n]，如果i < j，且A[ i ]>A[ j ]，则称(A[ i] ,A[ j] )为数组A中的一个逆序对。例如，数组（3，1，4，5，2）的逆序对有(3,1),(3,2),(4,2),(5,2)，共4个
要求交换次数，也就是求逆序对的个数。
注意这里因为数据较大，要用__int64定义num（两条下划线）
代码如下：
#include<stdio.h>
#include<stdlib.h>
__int64 num; //这里要用__Int64（注意是两条下划线）
int a[1000000], b[1000000];void fix(int *a,int*b,int left,int mid,int right)
{ //合并函数int i = left;int j = mid+1;int k = left;while (i < mid+1&&j<right+1)//这里都是+1，mid和right都可以取到{if (a[i] <= a[j])b[k++] = a[i++];else{b[k++] = a[j++];num += mid - i+1;//如果后面有个数小于前面，在前面序列中有mid-i+1个数比他大，也就是逆序数为mid-i+1，前i-1个都是小于后面这个数的}}while (i != mid+1)//如果一个序列提前走完，把另个序列剩下的全赋值到后面b[k++] = a[i++];while (j != right+1)b[k++] = a[j++];for (i = left; i <= right; i++)a[i] = b[i];
}void sever(int*a,int*b,int left,int right)
{ //建树函数int mid;if(left < right){mid = (left + right) / 2;sever(a, b, left, mid);sever(a, b, mid + 1, right);//先递归到底，再自底向上合并fix(a, b, left, mid, right);}
}int main()
{int n,i;while (scanf("%d", &n), n != 0){num = 0;for (i = 0; i < n; i++)scanf("%d", &a[i]);sever(a, b, 0, n-1);printf("%I64d\n", num);//这里要用%I64d(i的大写)}return 0;
}求逆序数最典型的方法是用树状数组，所以这道题还可以用树状数组做
代码如下：
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <algorithm>
using namespace std;const int maxn= 500005;
int aa[maxn];//离散化后的数组
int c[maxn]; //树状数组
int n;struct Node
{int v;int order;
}a[maxn];bool cmp(Node a, Node b)
{return a.v < b.v;
}int lowbit(int k)
{return k&(-k); //基本的lowbit函数
}void update(int t, int value)
{ //即一开始都为0，一个个往上加（+1），int i;for (i = t; i <= n; i += lowbit(i))c[i] += value;
}int getsum(int t)
{ //即就是求和函数，求前面和多少就是小于它的个数int i, sum = 0;for (i = t; i >= 1; i -= lowbit(i))sum += c[i];return sum;
}int main()
{int i;while (scanf("%d", &n), n){for (i = 1; i <= n; i++) //离散化{scanf("%d", &a[i].v);a[i].order = i;}sort(a + 1, a + n + 1,cmp);//从1到n排序,cmp容易忘memset(c, 0, sizeof(c));for (i = 1; i <= n; i++)aa[a[i].order] = i;__int64 ans = 0;for (i = 1; i <= n; i++){update(aa[i], 1);ans += i - getsum(aa[i]); //减去小于的数即为大于的数即为逆序数}printf("%I64d\n", ans);}return 0;
}