归并排序
“然而，”路由器说道，“快排的魔法是不稳定的……你的代码最终没有通过啊怎么办？”
“啊？那那……”勇者支支吾吾。 于是，他们只好造访了照相馆，借来了一本魔法书，但是魔法书经过风吹日晒所以代码丢失了，不过他的解释步骤还是很明显的。 “……那么想必看到这里的魔法师一定都会了神奇的桶排序了，我们可以借用这个思想来解释下接下来要讲的魔法……” “归并排序，O(NlogN)” “我们首先将整个数据分成两半，将每一半放在一个桶里面，然后对产生的新桶重复这个动作，一直到无法继续分下去（也就是桶里只剩下了一个元素为止）。” “之后就是惊心动魄的排序环节了。我们将每一个从一个桶里面分裂出来的两个桶称作同类，此时我们所需要做的，就是将同类桶进行排序，合并成原先分裂的桶，然后继续将同类桶排序……” “恩，没了……”路由器指了一下残叶，“来吧，我们来写代码吧……” 代码如下：#include#include #include #include #include using namespace std;int n,a[1000111],t[1000111];void msort(int x,int y){ if(x==y) return; int mid=(x+y)/2; msort(x,mid); msort(mid+1,y); int l=x,r=mid+1,j=x;//l左指针，r右指针，j当前数位 while(l<=mid&&r<=y)//比较，落下小的 { if(a[l]<=a[r]){ t[j]=a[l];l++;j++;//左指针++，当前数位++ } else{ t[j]=a[r];r++;j++;//右指针++，当前数位++ } } while(l<=mid){ //将剩余没落下的数字按顺序落下 t[j]=a[l];l++;j++; } while(r<=y){ t[j]=a[r];r++;j++; } for(int i=x;i<=y;i++)a[i]=t[i];//更新数组为排序后的数组 }int main(){ scanf("%d",&n); for(int i=1;i<=n;i++) { scanf("%d",&a[i]); } msort(1,n); for(int i=1;i<=n;i++){ printf("%d ",a[i]); } return 0;}
逆序对问题
“然而，这个魔法的作用却不只是排序，因为排序大部分情况下都是sort，所以我们可以用来解决……”
“逆序对问题”
（OpenJudge 7622）
总时间限制: 1000ms内存限制:
65536kB 描述 在Internet上的搜索引擎经常需要对信息进行比较，比如可以通过某个人对一些事物的排名来估计他（或她）对各种不同信息的兴趣，从而实现个性化的服务。对于不同的排名结果可以用逆序来评价它们之间的差异。考虑1,2,…,n的排列i1，i2，…，in，如果其中存在j,k，满足 j < k 且 ij > ik， 那么就称(ij,ik)是这个排列的一个逆序。
一个排列含有逆序的个数称为这个排列的逆序数。例如排列 263451 含有8个逆序(2,1),(6,3),(6,4),(6,5),(6,1),(3,1),(4,1),(5,1)，因此该排列的逆序数就是8。显然，由1,2,…,n 构成的所有n!个排列中，最小的逆序数是0，对应的排列就是1,2,…,n；最大的逆序数是n(n-1)/2，对应的排列就是n,(n-1),…,2,1。逆序数越大的排列与原始排列的差异度就越大。
现给定1,2,…,n的一个排列，求它的逆序数。输入
第一行是一个整数n，表示该排列有n个数（n <= 100000)。 第二行是n个不同的正整数，之间以空格隔开，表示该排列。 输出 输出该排列的逆序数。 样例输入 6 2 6 3 4 5 1 样例输出 8提示：
1.利用二分归并排序算法（分治）； 2.注意结果可能超过int的范围，需要用long long存储。好的，为什么说归并排序可以解决这个问题呢？还记得归并排序的原理吗？实际上，归并排序已经将所有的区间都给我们划分好了，所以我们只需要求出每个区间的逆序对有几个就可以了。
而且归并排序因为每归并一次都会排好序，所以我们的计算也可以变得更加简单（详情看注释）。
那么附上代码吧，也没什么好讲的：#include#include #include #include #include using namespace std;int n,a[1000111],t[1000111];long long ans = 0;void msort(int x,int y){ if(x==y) return; int mid = (x + y) /2; msort(x,mid); msort(mid+1,y); int l = x, r = mid+1, j = x; while(l<=mid && r<=y) { if(a[l]<=a[r]){ t[j] = a[l]; j++;l++; } else{ t[j] = a[r]; r++;j++; ans += mid-l+1;//在l与mid区间里面每一个数对于r来说都是它的逆序对 } } while(l<=mid){ t[j] = a[l]; j++;l++; } while(r<=y){ t[j] = a[r]; r++;j++; } for(int i=x;i<=y;i++)a[i] = t[i];}int main(){ scanf("%d",&n); for(int i=1;i<=n;i++) { scanf("%d",&a[i]); } msort(1,n); printf("%lld",ans); return 0;}