二路归并排序

引⾔： ⼆路归并排序采⽤把⼀个数组分割为单独的元素并且相邻两组合并的同时排序的⽅法进⾏数组的排序。 具体的实现在任何⼀本数据结构书中都有描述， 也不难理解。
今天我们来说说如何在归并的基础上，研究逆序对问题（给出完整 C 语⾔代码，已编译）
我们以 【7， 5， 6， 4】 这个数组为背景
通过层层递归拆分为 【7】 【5】 【6】 【4】 四个单独的部分， 然后采⽤⼆路归并 （相邻两个进⾏合并且同时从⼩到⼤排序） ， 得到【5， 7】和【4，6】 两个部分。 然后继续⼆路归并得到 【4， 5， 6， 7】 序列。
【注：在⼀次归并开始时， low指向左分区的第⼀个结点不变， i =low指向左分区第⼀个结点， mid指向左分区最后⼀个结点不 变， j=mid+1 ， j指向右分区第⼀个结点， high指向右分区最后⼀个结点不变】
我们来分析上述过程的细节： 其中 7， 5进⾏排序时， i 指针指向7， j指针指向5。 我们⼼⾥把7 和5当作两个已经排好序的序列，所以当出现arr[i]>arr[j]的时候， 也就是前⾯分区的某⼀项⼤于后⾯分区的某⼀项时， 前⾯分区从第i项到分区最后⼀个数（mid） 都会⽐这个a[j]⼤， 所以类似⼈脑计算的模式， 锁定这个⼩的数字， 然后找有多少个⽐他⼤的数就⾏， 因此我们让计数器的值count=count+mid-i+1（i到mid ⼀共有mid-i+1个数。同理我们来看看【5，7】 和【4，6】 两个下⼀步构建好的待归并的分区， 当i指向5， j指向4时，5⼤于4，⼜因为每个待归并的分区都是递增的， 所以5和7都要⼤于4，所以仍然是count=count+mid-i+1
由此分析， 我们发现其实归并的核⼼就是把两个已经排好序的序列再次进⾏排序， 借助这⼀特点， 我们不难发现其中的逻辑规律恰好可以⽤来求逆序对的数量。
下面给出 求有序数组逆序数的C语言代码。

// A code block
var foo = 'bar';

// An highlighted block
#include
#include
int n; // 全局变量 n 为了⽅便下⾯ malloc 
int count=0;// 统计逆序对的个数
int *B=(int*)malloc(n*sizeof(int));// 全局变量辅助数组n 如果要⽤户⾃定义，需要设为全局变量
void merge(int *A,int l ow,int mid,int high){     
 int i,j,k; //i指向左数组，j指向右数组，k指向原数组
 for(k=low;k<=high;k++){
   B[k]=A[k];//复制到B数组中
 }
 for(i=low,j=mid+1,k=i;i<=mid&&j<=high;k++){
   if(B[i]<=B[j]) A[k]=B[i++];//⼩的放回A中，并且i++ 
   else {A[k]=B[j++];//⼩的放回A中，并且j++
   count=count+mid-i+1; //前⼤于后，说明左分治数组剩余元素（包括这个）都⽐右边这个B[j]⼤，所以逆序对数+mid-i+1
   }
 } 
// 下⾯两个不会同时执⾏，否则上述循坏还没结束 
 while(i<=mid) A[k++]=B[i++]; 
 while(j<=high) A[k++]=B[j++];
} 
void merge_sort(int *arr,int low,int high){  
 if(low
   int mid=(low+high)/2;
   merge_sort(arr,low,mid);//先拆
   merge_sort(arr,mid+1,high);
   merge(arr,low,mid,high);//拆到最⼩2元的时候开始归并
 }
} 
int main(){
 int n;
 printf("input n:");//数组⼤⼩
 scanf("%d",&n);
 int arr[n];
 printf("input arry:");//输⼊序列
 for(int i =0;i 
 scanf("%d",&arr[i]); 
 } 
 printf("ordered arry:");// 输出序列
 merge_sort(arr,0,n-1); 
 for(int i =0;i 
 printf("%d", arr[i]); 
 } 
 printf("逆序对的个数是%d",count); //输出逆序对的个数 
}

n阶行列式概念
∣ a 11 a 12 ⋯ a 1 n a 21 a 22 ⋯ a 2 n ⋮ ⋮ ⋱ ⋮ a n 1 a n 2 ⋯ a n n ∣ = ∑ j 1 j 2 … j n ( − 1 ) τ ( j 1 j 2 … j n ) a 1 j 1 a 2 j 2 … a n j n left | begin{array}{ccccc} a_{11} &a_{12} &cdots &a_{1n} \ a_{21} &a_{22} &cdots &a_{2n} \ vdots &vdots &ddots &vdots \ a_{n1} &a_{n2} &cdots &a_{nn} \ end{array}right | = sum_{j_1 j_2 … j_n} (-1)^{tau(j_1 j_2 … j_n)} a_{1 j_1}a_{2 j_2} … a_{n j_n} ∣∣∣∣∣∣∣∣∣​a11​a21​⋮an1​​a12​a22​⋮an2​​⋯⋯⋱⋯​a1n​a2n​⋮ann​​∣∣∣∣∣∣∣∣∣​=j1​j2​…jn​∑​(−1)τ(j1​j2​…jn​)a1j1​​a2j2​​…anjn​​