归并法排序和逆序数问题（分治）算法,排序算法,分治算法weixin43802793的博客-

一、归并排序（分治法）
分治法，顾名思义，先“分”后“治”。
分——分解子问题，直到能在O(1)时间复杂度解决，归并排序问题中即是将一个元素数目为N的序列分成单个元素（或者视为单个元素对象），所耗费的时间为log2 N。

数组[49, 38, 65, 97, 76, 13 ,27]
分解为下面初始序列：

治——归并排序，实时更新子序列排序状况，时间复杂度为N。

二、逆序对
逆序对：对于给定的一段正整数序列，逆序对就是序列中 ai>aj 且 i<j 的有序对。
逆序数：一个排列所拥有逆序对的个数即为该排列的逆序数。

解题思路：在归并排序的基础上寻找逆序对；在每次合并之前，先计算逆序对数，左右两组数此时皆是从小到大的顺序排列。若左边第一个数大于右边第一个数，则左边剩下的数皆可和右边第一个数形成逆序对；此时继续看右边第二个数，比较左边第一个数和右边第二个数，以此类推。若左边第一个数小于右边第一个数，则比较左边第二个数和右边第一个数，如上述同样方式类推。

#include<bits/stdc++.h> using namespace std; int sum = 0;//记录逆序对的个数  void MergeAndCount(int* num,int* result, int start, int end){ int Lmark = start; int mid = (start + end)/2; int Rmark = mid; int rltmark = start; int temp1 = Lmark; int temp2 = Rmark; //基于现有排序计算逆序对的个数  while(temp1<mid && temp2<end){ if(num[temp1] > num[temp2]){    sum+= (mid-temp1);    temp2++; } else{    temp1++; } } //执行下一轮排序  while(Lmark<mid && Rmark<end){ if(num[Lmark] >= num[Rmark]){    result[rltmark] = num[Rmark];    rltmark++;    Rmark++; } else{    result[rltmark] = num[Lmark];    rltmark++;    Lmark++; } } while(Lmark<mid){   result[rltmark] = num[Lmark];   rltmark++;   Lmark++; } while(Rmark<end){   result[rltmark] = num[Rmark];   rltmark++;   Rmark++; } } void mergeSort(int* num,int* result, int start, int end){ if(end - start == 1)//只有1个元素  return; else{ mergeSort(num, result, start, (start+end)/2); mergeSort(num, result,(start+end)/2,end); MergeAndCount(num,result,start,end); for(int i=start; i<end; i++)    num[i] = result[i]; } } int main() { int n;  cout<<"序列所含元素数目："<<endl;  cin>>n; int *num = new int[n]; int *result = new int[n];  cout<<"输入元素："<<endl; for(int i=0;i<n;i++)   cin>>num[i]; mergeSort(num,result,0,n);  cout<<"排序后的序列："<<endl; for(int i=0;i<n;i++)   cout<<num[i]<<" ";  cout<<endl;  cout<<"该序列的逆序数："<<endl;   cout<<sum<<endl; return 0; }码片 

运行结果：