归并与逆序数 前言简介归并排序求逆序数
前言
归并排序是一种非常重要的排序，因此，我觉得学会归并排序十分重要。
简介一般排序会用到冒泡排序，虽然冒泡排序是一种稳定的排序算法，但是时间复杂度是O(log(n2))，时
间复杂度就有一点点高，也许你会说用快速排序，没错，快速排序也能很快的将一串数字排序好，但
是快速排序针对一些数据很快，也会针对有些数据很慢，因为快速排序并不是稳定的排序算法，而今
天我们要介绍的归并排序是既快又稳定的排序，他和快排快速的原因是一样的都是分治，就是把一个
个问题分化处理，分成一个个小问题处理，也就是分成一个个小序列排序，而不是冒泡那样每一次都
要考虑没有排序的数。但是归并函数有个美中不足的地方，就是他是拿空间换时间。
归并排序接下来讲归并排序到底是怎么排序的，归并函数需要用到俩个子函数，一个递归函数和一个合并的函
数，和并的函数作用就是将俩个有序数列合并，这个比较简单就不多作解释。归并函数就是将一个个
问题深入，一直自己调用自己，把本序列分成俩半，每一半都会调用一次，调用到序列只有一个后就
会停止调用，因为序列只有一个的时候肯定是有序的，就不需要排序。如果不是1的话肯定是到了序列
里面只有俩个数，因为多于俩个它还会继续调用自己直到为1个就会停止，2个的一半就是一个所以返
回到还有俩个的递归处，俩个再调用合并函数，因为俩个分成俩半，每一半里面只有一个数字，所以
这俩个序列一定是有序的序列，然后将这俩个数连接好在放回原位，这俩个数就已经排好序了，再返
回到就到了还有4个数的时候，前面俩个和后面俩个就是上一步全部排好序了，再合并也是排好序的，
然后，一直归，直到归到没分治的状态，再合并，就已经排好序整个序列了。
话不多说，上代码。
#include<stdio.h>void hbfun(int a[],int b[],int front,int mid,int last){ //合并函数 int i,j,k; for(i=front,j=mid+1,k=0;i<=mid&&j<=last;) { if(a[i]<=a[j])b[k++]=a[i++]; else { b[k++]=a[j++]; } } while(i<=mid)b[k++]=a[i++]; while(j<=last)b[k++]=a[j++]; for(i=front,j=0;j<k&&i<=last;)//原位放回去 a[i++]=b[j++];}void gbfun(int a[],int b[],int i,int j){ //递归函数 if(i>=j)return ;//只有一个的时候 else { int mid=(i+j)/2;//取中间点 gbfun(a,b,i,mid);//前半部分 gbfun(a,b,mid+1,j);//后半部分 hbfun(a,b,i,mid,j);//将前后部分合并 }}int main(){ int n; while(~scanf("%d",&n)) { int a[100010];//存储输入的数 int b[100010];//用来合并需要所开的空间 int i,j,k; for(i=0;i<n;i++)scanf("%d",&a[i]); gbfun(a,b,0,n-1); for(i=0;i<n;i++)printf("%d ",a[i]); printf("n"); }} 求逆序数求逆序数的方法不止归并这一种，但是归并求逆序数是很简单的的，所以我还是建议大家学习一下。
首先我们知道归并就是在分治，分成前后俩部分分别排序，所以求逆序数就可以在合并函数的时候计
算，因为前面和后面部分分的很清楚，前面比后面大时就说明在前面这个序列里面，这个数和这个数
后面的所有数都大于此时比的后面序列的这个数，此时就拿一个计数变量将这些数字加起来即可。
#include<stdio.h>int sum=0;//定义全局变量计数 void hbfun(int a[],int b[],int front,int mid,int last){ //合并函数 int i,j,k; for(i=front,j=mid+1,k=0;i<=mid&&j<=last;) { if(a[i]<=a[j])b[k++]=a[i++]; else//前面比后面大的时候，而且不包括等于的 { sum+=mid-i+1;//加1是因为下标是从0开始实际上会少一个 b[k++]=a[j++]; } } while(i<=mid)b[k++]=a[i++]; while(j<=last)b[k++]=a[j++]; for(i=front,j=0;j<k&&i<=last;)//原位放回去 a[i++]=b[j++];}void gbfun(int a[],int b[],int i,int j){ //递归函数 if(i>=j)return ;//只有一个的时候 else { int mid=(i+j)/2;//取中间点 gbfun(a,b,i,mid);//前半部分 gbfun(a,b,mid+1,j);//后半部分 hbfun(a,b,i,mid,j);//将前后部分合并 }}int main(){ int n; while(~scanf("%d",&n)) { int a[100010];//存储输入的数 int b[100010];//用来合并需要所开的空间 int i,j,k; sum=0;//每次计数前将它初值赋值0 for(i=0;i<n;i++)scanf("%d",&a[i]); gbfun(a,b,0,n-1); for(i=0;i<n;i++)printf("%d",a[i]); printf("n"); printf("%dn",sum); }}