- //find_invertion.cpp:
- //*************************************************************************
- //Remarks:
- //设A[1..n]是一个包含n个不同数的数组,如果在i<j的情况下,有A[i]>A[j],
- //则称( i , j )为A中的一个逆序对(inversion),现给定数组,求其中的逆序对
- //本算法的基本思想是通过修改归并排序的过程,将复杂度下降到O(nlgn)。
- //*************************************************************************
- #include "find_inversion.h"
- #include <cassert>
- //逆序对的个数
- int inversion_num;
- void merge_partion(int * a , int low ,int high)
- {
- assert(a!=NULL&&high>low);
- while(low<high)
- {
- int mid= low+(high-low)>>1;
- merge_partion(a, low , mid);
- merge_partion(a, mid+1, high);
- merge_count(a, low ,mid, high);
- }
- }
- void merge_count(int *a , int low ,int mid ,int high )
- {
- int left_lenth=mid-low+1;
- int right_lenth=high-mid;
- int * lefta= new int[left_lenth];
- int * righta=new int[right_lenth];
- for (int i=0;i<left_lenth;++i)
- {
- lefta[i]=a[low+i];
- }
- for (int i=0;i<right_lenth;++i)
- {
- righta[i]=a[mid+1+i];
- }
- //归并过程 并统计逆序对的个数
- int j=0,k=0;
- int i=low;
- while (j<left_lenth&&k<right_lenth)
- {
- if (lefta[j]<=righta[k])
- {
- a[i++]=lefta[j++];
- }
- else
- {
- a[i++]=righta[k++];
- inversion_num+=left_lenth-j;//逆序对的统计
- }
- }
- while (j<left_lenth)
- {
- a[i++]=lefta[j++];
- }
- while (k<right_lenth)
- {
- a[i++]=righta[k++];
- }
- }
- //该片段来自于http://www.codesnippet.cn/detail/220920136038.html
来源: http://www.codesnippet.cn/detail/220920136038.html